Take the Lithium
In certain respects, an ideal electrical capacitor remains the perfect energy storage vehicle. Pure, pollution-free electrons provide the energy, with little downside if we can eliminate the leakage currents and up the voltage without the risk of electrical breakdown.
Toshiba has a press release describing a Lithium-Ion battery with many of the same characteristics of a capacitor, namely extremely fast recharge. In Toshiba's case they claim recharge times of less than a minute.
The unspecified voltage causes me a bit of concern. They claim not to reach the 3.6 volts of standard Li+. Much like traditional capacitors, many of the charging problems go away as you reduce the voltage.
Energy = CV2
Alas, the energy contained within scales as the square of the voltage applied. We will have to wait and see on this one. Likely great for impatient users of MP3 players and such, but maybe not for that hybrid vehicle.
Treehugger also brings up the Vanadium Redox battery. Curiously, the Australian web site proclaiming its invention looks a bit stale.