Or midi breath control, where you have to modulate your breath pressure to get shift, alt, alt+shift, control, etc. Surely most people can handle 4 bits of resolution with their breath power, right?

Yes, a Bluetooth 6DOF accelerometer/orientation sensor/magnetometer affixed to each shoe and you're sorted. I've long wanted to see a pair of such sensors set up as MIDI controllers. If you're using them on uneven or moving surfaces you might want separate sensors for heel and toe.