I've kept a modest watch on battery technologies, and there are some interesting developments, though most are fairly modest.
You've got the fundamental problem that battery energy storage densities by weight are ~1/100 - 1/50 that of liquid hydrocarbon fuels. Synthetic analogs of petrol, kerosene, and diesel would be quite useful (though expensive). All but irreplaceable for some uses (heavier-than-air flight, marine propulsion).
Among batteries, you have:
1. Liquid / molton salt batteries. Some of these have highly abundant substrates. The problem is the 300-600C+ temperatures they operate at. Especially in vehicle applications.
2. Metal-air batteries. Iron and aluminium particularly. Here the oxidation is supplied from air. You're consuming the (anode?) in use, and it's got to be replaced, but that can include recycling. Abundant but problematic.
3. Fuel cells. A reaction, typically of hydrogen and oxygen, producing electron flows. The problem is the reaction chamber, which usually requires scarce catalysts (e.g., platinum) which are a) expensive and b) rarer than lithium.
4. Advanced allotropes. Carbon or silicon or other materials which are abundant but offer unique properties in new molecular forms. While this is well outside my area of expertise, it's an un(der) explored area which might pack some suprises.
5. Biocells. Life does some amazing things with enzymes and other agents, including maintaining an exceptionally high voltage potential across cell membranes (see Nick Lane's book, recently mentioned here via Bill Gates). Humans utilising biological mechanisms to provide electricity might offer another out, though this again is highly speculative.
The advantage of my #s 4 & 5 is that they could rely on highly abundant elements arranged in complex molecules to perform desired functions. Experience suggests that such molecules are difficult to come up with, degrade quickly, and have narrow operating bands in which they're viable. But at least the abundance constraint is removed.
Sodium batteries have been around since the 1960s.[1] They're a high-temperature battery, 90°C and upwards. Ford built some experimental vans with sodium-sulfur batteries in 1991. Two of them caught fire. That technology was abandoned for mobile applications.
There's still interest in this for stationary energy storage on power-grid scale. But not for mobile. Sodium catches fire if exposed to air.
Sodium-ion batteries aren't necessarily the dead end you might think.
Faradion has been working on portable batteries w/ decent energy density (~150 Wh/kg), excellent charge-discharge performance (93% capacity after 1000 cycles) and competitive costs: http://www.faradion.co.uk/about/news/2015/05/489/
Sodium batteries run at very high temperature and are finicky. They have been used for decades on submarines where they can be managed by trained personnel and where a large heat sink is available. I would be wary of consumer sodium based batteries.
I think that's sodium-sulfur batteries. There is work being done on sodium ion batteries. And also aluminum ion batteries. In thoery these are both similar to lithium ion batteries. In practice figuring out how to produce high quality ion batteries is not easy.
another one is potassium, and giving that the future is metal-air batteries, potassium works great there (its oxide seems to behave better for recharging in that scheme than lithium's)
Wrt. possible short-term lithium supply issues, i can see how Musk would just build a new mine operation if necessary, like a Giga-ship to mine it from seawater :)
