Praticamente qualquer proxy / gateway fará isso. Lula é boa. O PFSense é uma boa solução completa se você não quiser fazer muito trabalho sozinho. Você pode instalar o PFSense em um servidor (um servidor virtual está OK) e, em seguida, instalar o plugin Squid para ele.
Em seguida, você aponta todos os seus computadores para a máquina do squid / PFSense como seu gateway, e seu gateway atual se torna o gateway da máquina do Squid / PFSense.
Então vai:
Computer > Squid/PFSense > Gateway
Voila.