Рекомендую Fedora, так как под неё заточена очень хорошая (бесплатная) 
биллинговая система http://www.traffpro.ru/ 
(сборка есть и для Дебиана, но лучше под Федорку ставить).

прокси-squid тоже нормально (особенно если надстройку Sarg + Wemin поставить), 
но через него не пустишь pop3,smtp, придется пробрасывать напрямую, 
что соответственно не даст учитывать трафик по этим портам. 

Если же биллинг (учет и блокировка трафика) вообще не нужен, 
то можно и правила iptables создать и открыть nat прозрачно.

Читать по биллинговым системам тут: 
http://linuxbill.blogspot.com/2007/12/linux.html

Читать по конфигурированию squid и iptables здесь: 
http://www.ingineer.ru/linux/