vorticey,
Just storing energy won't work, because the aircraft needs so much of it. If you squeeze air into a bottle and then let it out into an engine, you get less than you put in. If you bring some gasoline, you get a tremendous return on its weight. For example, a pound of air squeezed to 90 atmospheres has about 2.6 million ft-lbs of stored energy in it. If it were used in 1 minute, it has a total of 78 Horsepower for that minute. If a pound of gasoline were compared, it has 14 million ft-lbs of energy in it, and delivers 424 Horsepower if burned in 1 minute.
In other words, fuel is about 5 times more weight efficient when compared to stored air. And we didn't figure in the weight of a compressed bottle as compared to a fuel tank. My guess is the bottle would have to be 5 to 10 times heavier than the fuel tank, a further penalty.
You have also pointed out why electricity is so poor in flying machines. Recall that the electric motor needs to have energy delivered to it, so it needs to be fed those enoumous amounts of energy to make the power, and that energy is hard to come by.
PS they breath helium at great depth because of nitrogen narcosis, not because of explosions. At high pressure, nitrogen is an anesthetic and makes you high! Helium only makes you talk like Donald Duck.