> Прописывал все правила на роутере, но похоже чего-то не хватает

Вестимо

iptables -t nat -A PREROUTING -i eth0 ! -s 109.0.0.110 -p tcp --dport 80 -j DNAT --to 109.0.0.110:3128

в грубом переводе "прероутинг на интерфейсе eth0, если НЕ источник..."

и

iptables -t nat -A PREROUTING -i eth0 -s ! 109.0.0.110 -p tcp --dport 80 -j DNAT --to 109.0.0.110:3128

в грубом переводе "прероутинг на интерфейсе eth0, если источник НЕ..."