Basic chemical reactions involving metals are out (batteries), cause we've hit the limits of electronegativity with lithium. Mechanical storage (springs, flywheels) have never been that great of an idea because of structural limits, and natural occurring chemicals have reached their limits of energy density and have pollution issues (such as the release of carbon to form CO2).

So what's left? Nuclear power, fusion, electric fields and artificial molecules. I don't see society accepting nuclear powered vehicles any time soon (though it works for submarines, destroyers and aircraft carriers; perhaps commercial shipping will convert as well if they can learn not to leave drunk 3rd mates in charge of steering through tight passages); and fusion research is still indicating that a lot of energy must go in to get any kind of return; so how about electric fields and artificial molecules?

* Artificial Molecules

So if we're thinking about making fuel, why not make something better than hydrogen gas. Carbon isn't the greatest since it produces CO2, so lets look for another core element to use. Hmmm, a lot of the other semi-metals are kind of noxious: Phosphorus, Sulfur, Gallium, Arsenic, Selenium, ..., Antimony, Lead. But there are two that aren't very heavy, and are fairly common: Aluminum and Silicon. Now Aluminum is a metal and probably not as common as sand (Si), so lets pick Si for starters.

So the first strategy would be to create long chains of it, like you do with carbon. Maybe: Si12H26
If you can't make chains of pure silicon, maybe we'll mix some carbon back into the mix, like: C7Si8H32

Playing with chemicals like this is pretty standard stuff. Its looking for fuels specifically that is driving this research. A lot of work is already being done to find a binder for hydrogen (like the DOE's proposed NaBH4). And then there's the rocket team at scaled.com that decided on a synthetic rubber (HTPB) as the fuel in their hybrid rocket motor (though more for reasons of availability and safety than energy density).

* Capacitors

This is probably the least SciFi of them all. In the last five to ten years, a new product line has popped into existence: super-caps. These have expanded the storage of electrons by orders of magnitudes (in terms of energy density). You have super-caps that are starting to rival lead acid batteries in terms of energy storage, and don't have any of the drawbacks of batteries: low discharge rates, fatigue, charging side effects, toxic chemicals, etc. Because of their high current cost, they're not replacing batteries in any wide spread way yet, but in some applications their being put in along side batteries for their benefits of fast current drain, and no recharging memory.

The coolest part is that current products are in no way up against any laws of physics, only limits of current manufacturing. The only theoretical limits for capacitors are the size of the electron, the size of the plate metal atoms, and creating enough of a gap. So in theory, with 100V charge in a 1 MF capacitor, you'd have 1.4 MWh's which could be compressed down to a device the size of a coffee cup. In comparison, a tank of gas is around 100kWh. (Thanks to Nils for opening his physics text book at correcting my original numbers.)