A proxy server is probably not the best solution in this case, seeing as it is difficult to configure clients this way. But, it seems that a lot of people have trouble understanding this sort of technology.
First, NT security policies do not affectInternet access no matter how your network is configured.
This all really depends on how your network is configured.
Are you using an NT box as your network gateway?
or Is your network gateway some sort of hardware router?
Assuming all your clients have their own Internet IP addresses, if your gateway is a NT server, I would suggest installing a firewall on the server to block packets being forwarded across the installed network cards and blocking access by IP address. Here you could also install a proxy server to better manage traffic, but this reduces some types of network access in a way that may be unacceptable.
If your gateway is a hardware router, utilize it's firewalling/forwarding features to block client access to the Internet. Here, you can also completely block all Internet access except for your proxy server (if you choose to use one) and use it to allow Internet access to your clients.
DHCP will only offhandedly affect Internet access. If you choose to use a firewall to prevent client access, your clients must have a static address in order to allow/disallow individual access rights, as you'll need to specify which IP addresses are allowed Internet access at your gateway and which are not.
Either choice, proxy or not, will require some sort of firewall at the gateway to prevent direct internet access from the clients.
Phew. I hope I helped someone.