Lo mejor forma para compartir la conexion es, sin duda, mediante NAT (network address translation)
Para ello, y partiendo de la base de que tengas ya las IP's estaticas (a ser posible un rango no accesible desde internet como puede ser el rango 10.x.x.x

) y te devuelva los ping entre los pc's y eso, deberas instalar un programa en el pc que tiene internet que te permita compartir la conexion a traves de NAT.
Yo entre todos recomiendo wingate, que es muy completo y esta muy muy bien, la unica pega es que es un poco dificil de configurar (hasta que uno se decide a leer el readme, todo hay que decirlo

).
Quiza haya alternativas freeware, pero yo no las conozco. Todo es cuestion de investigar un poco
El caso es que deberas instalar este porgrama, u otro, y con eso el pc con conexion a internet ya estara dispuesto para compartir la conexion, pero ahora te falta configurar el cliente.
Para ello, tienes que configurar el cliente de esta manera:
1- Puerta de enlace (o gateway): IP del pc con internet
2- DNS: IP del servidor DNS del ISP con el que conectes. Visitando la web de tu ISP o llamando por telefono sabras cual es
3- No activar PARA NADA nada relacionado con proxy
NAT tambien permite compartir la conexion entre diferentes SSOO, asi que podras poner un linux de cliente teniendo windows como servidor o un servidor linux con un windows como cliente, etc ...
Saludos!