I dont know why people are sticking to batteries - even now.. with all their inherent dangers and incompatibility with the current gas based vehicle systems?
My thinking is in the following lines -
A + B --electricity--> C
C + O2 -> A + B + Heat
In this case, we should be able to store C only (similar to petrol), and whenever needed, just jack in the power.
Wishful thinking, but possible, I guess.