I think you have mistaken the usefulness of a "proxy" server.
Proxy servers typically only redirect HTTP traffic on certain ports. If you want your machines behind the firewall to be able to "see" the internet on all ports, you will need to enable NAT on the firewall.
After you do this, you can safely just remove the proxy server, in my opinion.
Enabling NAT varies depending on the distribution and the kernel version. It is actually very easy to do. You should be able to find a HOWTO someplace on setting that up.
Basically, NAT allows your router to send packets to the Internet on behalf of the machines connected to your network. When the "Internet" responds, the router remembers which machine asked for the information and forwards it. In this way, the router becomes a transparent intermediary. NAT is done at the Kernel level, so you might have to recompile your kernel depending on your current configuration.
Hope I pointed you in the right direction!