NAT - это всего-лишь подмена адресов (потому и называется Network Adress Translation), а роутинг - это механизм в TCP/IP стеке (который использует в том числе и NAT).
То есть, механизм такой: маскарадер ловит пакет из локальной сети с адресом во внешнюю сеть, меняет в нем source_ip и source_ip_port и после этого помещает пакет в TCP/IP стек, который роутит пакет во внешнюю сеть. Таким образом, NAT просто не можен работать без роутинга. :-)
вообще-то, не TCP/IP, а только IP :) Роутинг, он же маршрутизация, есть процесс нахождения оптимального пути IP-пакета между хостами в гетерогенной сети :)
То есть, настраиваешь 2 интерфейса (пусть будет на eth1 192.168.1.1 и на eth0 W.X.Y.Z - адрес из внешней сети). Прописываешь роутинг между этими двумя сетями типа:
route add -net 192.168.1.0/255.255.255.0 eth1
route add -net W.X.Y.Z/тра-ляля eth1
Дефолтовый роутер для маскарадера, понятное дело должен быть роутер из внешней сети.
включаешь ip_forwarding (echo 1 > /proc/sys/net/ipv4/ip_forward) и tcp_syncookies (echo 1 > /proc/sys/net/ipv4/tcp_syncookie), ну а дальше прописываешь через iptables правило маскарадинга типа:
iptables -A POSTROUTING -s 192.168.1.0/255.255.255.0 -d 0.0.0.0/0.0.0.0 -j MASQ
(или нечто подобное - сейчас по памяти точно написать не могу)
Всем компам в подсети 192.168.1.0 скажи, что маршрутизатор у них 192.168.1.1 и будет тебе счастье.