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.

802.1X. This is not something that is trivial to implement, it requires the appropriate security infrastructure to back it up (associated user accounts, etc), but it as far as I know, the only way to even get close to what your auditors are asking for.

It is supported by Windows, Linux, iOS (both the Apple and Cisco versions, so its good for iPads and iPhones), OS X, Windows Mobile (even 2003, vomit), Blackberry, Android, virtually every device that's out there needs to support 802.1X.

What you're looking for is called port security (on Cisco switches at least). You need managed switches for this kind of access control.