Você pode fazer com que todos eles usem o mesmo IP falso para o servidor DNS e direcionar para o DNS correto de acordo com a WAN selecionada.
Não sei como você determina como o tráfego vai sair (qual de seus dois ISPs ...), mas eu diria que você tem dois NICs WAN, vamos chamá-los de eth0 e eth1.
Vamos supor que seu IP de DNS falso seja 1.2.3.4 e que o DNS "correto" para eth0 seja 2.2.2.2 e o DNS "correto" para eth1 seja 3.3.3.3.
Eu acredito que isso daria certo:
iptables -t nat -I POSTROUTING -o eth0 -d 1.2.3.4 -j DNAT --to-destination 2.2.2.2
iptables -t nat -I POSTROUTING -o eth1 -d 1.2.3.4 -j DNAT --to-destination 3.3.3.3