Metal-air batteries (lithium is one type) can do pretty good, not quite as good as reacting oils with oxygen. The metals release a lot of energy when combined with oxygen, sort of trying to return to their original "ore" state. I think aluminum and zinc are the best candidates. Energy storage technology has had an amazing lack of improvement on a cost/Joule basis. The first self-start cars used lead acid and on a Joule per constant dollar basis a lead acid battery cost the same in the 1930's from the Sears mail order catalog as it does today from Walmart. All the technological advances in mining, world trade, and Walmart efficient distribution were not able to offset the increased cost of energy needed to mine, fabricate, and transport and pollution control regulations. Alkaline AA batteries appear to cost the same today on a constant dollar basis as they did in the 1980s, if not more, and we still normally use them instead of lithium or NiMH.
Supercapacitors can't compete with batteries. There were several companies 10 years ago jumping onto that bandwagon to get funding by making unproven and unphysical claims. EEStor was the one with the most success, sucking $40 M out of equity markets, even from KPCB investors. They had the biggest success because they were the most successful fraud. The fundamental problem with capacitors is that the internal chemical bonds do not change except by being stretched (unless it is a pseudo-capacitor like electrolytics or a graphene-type). A high dielectric constant is the result of the dipoles affecting each other: you apply a voltage and they begin to separate, but by their separation the 2 neighboring dipoles above and below have their opposite attracting charges get closer to the charges of the dipole in the middle, helping pull each other apart. So there is a feedback between the dipoles that is not storing a lot of energy. You can't raise the voltage much because the bonds break. The best (energy storage) capacitors will have a low dielectric constant, nearly as low as air (k=1).
Batteries on the other hand have electrons that cross the plates and go inside the "dielectric", changing the physical bonds. This is why they can't be cycled "forever" like a true capacitor, and why electrolytics are half battery and don't last forever. Graphene type pseudo-capacitors (half battery by my definition of battery) can only do a little bit better on an energy/weight basis than lead-acid and compressed air. The graphene type is a mixture of polarizing the material and letting electrons get inside the "dieletric" to change the bonds right there at the surface (not really entering too far, but not following the ideal capacitor equation exactly either).