I have a special interest in compressed air, since I have a collection of air rifles. To give you an idea about energy density, there are very few air rifles powerful enough to challenge the least powerful (22 rimfire) firearms, and the airguns that can do this tend to be quite expensive.
Here's my favorite air rifle, check it out:
http://users.htcomp.net/tbelding/FX/tarantula.html
The energy density of air is limited by the strength of your storage bottle. The stronger it is, the higher pressure it can contain. My FX Tarantula tops out at 200 bar, which is 3,000 PSI. However, the pressure drops steadily as you use air out of it, so it's not a constant power source. It requires complicated valving to keep the power from fluctuating too much.
By way of comparison, firearms develop internal pressures as high as 50,000 PSI, or a bit higher. There really is no contest. Firearms have been called the world's simplest internal combustion engines.
The other thing to remember is that there's always a certain degree of inefficiency when compressing air, due to the diesel effect. Compressed air becomes hot, and the heat then diffuses away and is lost. There's no way around it.
Getting back to cars. . . The new carbon-fiber storage tanks allow higher pressure air to be stored with less weight, so maybe these things could have competed with electric cars -- if we were still stuck with lead-acid batteries. But battery technology has moved on, so I don't really see the point of fooling with compressed air now.
There's also a safety concern, as a ruptured air tank would go up like a bomb. It's much more dangerous than gasoline. This is why I cringed when GM showed off the Sequel with its 10,000 PSI hydrogen storage tanks! All it would take is one "road rage" or drive-by shooting incident, with a bullet striking the tank, and that sucker could be headed for orbit. "Houston, we have a problem!"