Eu acho que você está no caminho certo com as marcas. Já passou algum tempo desde que usei isso, mas acho que você precisa usar uma tabela de roteamento separada para cada link WAN. Semelhante à informação documentada aqui .
Então, por exemplo, você configuraria algo como o seguinte para a primeira conexão WAN e repetiria para cada WAN adicional.
(substitua / defina $ {wan ...} variáveis com valores apropriados)
# Get/Assign WAN1 gateway interface/IP
wan1_interface=eth0
wan1_gateway_ip_address="$(ifconfig br0 | grep 'inet addr:' | cut -d ':' -f2 | cut -d ' ' -f1)"
# Create routing table for WAN1
ip route replace default via ${wan1_gateway_ip_address} dev ${wan1_interface} table 100
ip rule add fwmark 0x7 table 100
# Setup policy for marking WAN1 traffic
iptables -t mangle -N wan1_policy
iptables -t mangle -A wan1_policy -j MARK --set-mark 0x7
# Mark traffic coming in on WAN1 interface
iptables -t mangle -A PREROUTING -i ${wan1_interface} -j wan1_policy
Peço desculpas se isso é um pouco grosseiro ou incompleto. Infelizmente sou um administrador do Windows na minha profissão. Então, eu não costumo mexer com a rede ou o lado Linux / Unix das coisas com frequência suficiente para ser muito fluente nesse nível. Porém, atualizarei a resposta se conseguir me lembrar de informações mais específicas dos cantos empoeirados do meu cérebro. :)
UPDATE: Encontrei um script antigo que usei e atualizei o exemplo acima com comandos mais precisos. Eu tive que ajustá-los para a sua situação (eu estava usando-os para direcionar o tráfego para uma conexão VPN), mas acho que eles devem ser bons agora.