Don't forget the exemption from motor vehicle legislation that we enjoy applies specificly to "bicycles with an auxilliary electric motor", so under existing legislation an air powered machine would be considered a motor vehicle. The air tank would also come within the scope of the stringent regulations and insurance requirements concerning pressure vessels.
So while it's possible it would be unlikely to be worth the considerable hassle involved.
For anyone determined enough air power tools are cheap enough and contain a tiny but powerful air turbine and reduction gear that could be used as the basis for a motor, and a divers SCUBA tank is a ready made tested and certified air tank.
Compressed air power is not a new idea, it was first used well over 100 years ago to power amongst other things
mining locomotives where a low fire risk power source was needed before the advent of safe portable electricity. The only problem was that the air tanks themselves were prone to explosion in the days before proper inspection and testing!