Si no te molesta dar internet a través de un proxy, squid es tu solución para muchos usuarios, es muy poderoso, si son muy pocos tal vez podrías usar tinyproxy pero nunca lo he usado, solo he escuchado buenos comentarios al respecto.
<br>un NAT generalmente se usa para dar servicio de internet sin necesidad de proxy, o para dar servicio web desde un pc que no tiene ip pública.<br><br>si instalas squid en ubuntu server, lo único que debes hacer es configurar los clientes para que lo utilicen, una vez instalas squid hay que hacer solo un par de configuraciones básicas y está listo para funcionar, de ahí en adelante depende de las restricciones que quieras aplicar, que para eso squidguard es fabuloso.
<br><br>"sudo aptitude install squid" y lees uno de tantos tutoriales en linea para arrancar con un proxy transparente, si es lo que quieres o uno configurado, si lo necesitas. Con el transparente el usuario no debe configurar nada.
<br><br>Inténtalo y nos cuentas.<br>