How do I force all devices on a network to register with IT before connecting, without vulnerability to Static IP-ing or MAC spoofing?

Context:

I'm an admin for a midsize corporate network with several overlapping wireless access points and an ethernet cabling infrastructure. To comply with a security audit, we were recently ordered to implement full device authorization on the network--not just a method for detecting rogue APs and the like, but a full "if your device isn't manually added by us, it can't connect to anything" system.

My first thought was: just create static DHCP MAC-to-IP bindings for everyone, manually, and have people with new devices come to me when they first set up their accounts. I told the auditors, and they said that whatever system we implement cannot be vulnerable to MAC address spoofing or static IP-ing, or else we will remain out of compliance.

I'm aware that there are products out there that will bind to your computer's network connection, and require you to authenticate against some centralized server in order to get network access, but my experience with those (and the Cisco AnyConnect VPN, which works similarly) has been that they can't run on all platforms. Since we have a BYOD environment (not my call), that wouldn't work.

Question:

What software can I run at the network level that prevents devices (any/all devices; arbitrary types/OSes on laptops, random mobile phones, tablets, etc.) from getting network access until I manually add them to our network (ideally without too much hassle during the addition process)? It needs to work similarly on both wired and wireless connections, and not be able to be bypassed by setting a device's MAC address or IP to that of an already-authorized device.

Because of the variety of devices we have, whatever solution we use should be centralized, without extra software requirements on the client. If there's something that fits the bill, but requires client software, I could probably convince management to use it if the client software worked on the majority of our devices (i.e. all *nix laptops, OSX, Windows (xp through 8), iOS, Android, Windows Mobile, BlackBerry), and the oddball users that weren't covered could just deal with it.