Now that you mentioned it, I think only USB Mass Storage was disabled, not the ports themselves. So the keyboard/mouse etc continue to work.
So Yubikey would work. It identifies itself as a Keyboard to the OS.
These are HID devices, because they need to do challenge/response with the website that's trying to authenticate. The old OTP YubiKeys were keyboards. Better than nothing but phishable.
They can be permanently connected to computer.
Yes but even such a solution would surely use some sort of existing internal interface such as USB or PS/2, even if in practice the wires are soldered directly to the motherboard? Otherwise you'd have to build special hardware, controller chips, develop and maintain the driver?
bluetooth?
Requires batteries. NFC is the obvious choice, and yubikey neo already supports that. Note that (going back to top-level parent comment) current yubikey neos cannot support U2F; all they say is U2F compatible devices will be available sometime [later] this year.