Ideal setup is to treat employees differently and the outsiders who come to office differently.All the employees should be put on a different network in a different firewall zone say trust(10.2.0.0/16) and the outsiders on another network on another firewall zone say trust2 (10.3.0.0/16)
You can provide access to the internet from trust and then whitelist the IP addresses as and when required from trust2(you should provide static addresses). This will give you better flexibility to on the policies for the organization
(for eg: if you want to give unrestricted internet access to employees and block certain sites from non employees)
Coming to NAP, I have not worked on it.But after some reading, it seems that Microsoft partners have released NAP clients for linux and MAC.
(http://kurtsh.com/2008/12/23/info-network-access-protection-nap-clients-for-linux-and-macintosh-are-available/)
I do not have prior experience using any of these clients, hence cannot comment on them, but you can make inquiries.They seem like commercial tools
If you are looking for non commercial tools, there is a possibility of using squid.Squid can prompt users for a username and a password.
http://www.linuxhomenetworking.com/wiki/index.php/Quick_HOWTO_:_Ch32_:_Controlling_Web_Access_with_Squid#Password_Authentication_Using_NCSA
http://www.cyberciti.biz/tips/linux-unix-squid-proxy-server-authentication.html
Yet another option would require help from your firewall.I have worked on Juniper Netscreens and they allowed authentication on the rule.So basically you configure authentication on the firewall rule that allows internet access and users will have to enter a username and password to get through.This is device dependent and you will need to check your firewall for such a feature.