Embora seja possível fazer isso tudo com o Linux, eu descartaria essa ideia e usaria o PFsense . É uma distribuição de roteamento / firewall baseada no FreeBSD. Eu acredito que ele deve fazer tudo que você precisa com sua configuração pronta, com apenas a adição do pacote do Squid para configurar um proxy SOCKS (ou transparente, se desejado). Eu uso o PFsense há anos e é um produto muito sólido, com uma ótima comunidade em torno dele.