O motivo pelo qual não funciona é porque você só pode modificar pacotes de certas maneiras em certas partes da pilha do netfilter. Modificar o destino ao sair é tarde demais. Você precisa modificá-lo no caminho.
iptables -t nat -A PREROUTING -p tcp --dport 80 -j REDIRECT --to-port 8118
Eu recomendo pesquisar as várias tabelas que compõem a pilha do netfilter.