OK, this will be sneaky but should work. Create two policies. One for people who will get Internet and one for people only allowed intranet.
Since you DON'T have a firewall or proxy, we are going to fake out the system. Make up a phony proxy name and configure it to be pushed down to all of your intranet only users. If they try to go out on the net, they will get an error because the proxy can't be contacted. Make sure you lock them out of changing the proxy settings.
For your Internet allowed people, I would lock them out of the Internet Options settigns too even though you are not configuring those settings for them. Lock down anything else specific to Internet users in this policy.