There's someone in Halifax researching Sodium Batteries, which would be a fair bit easier to find than lithium, though less effective.
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.
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.
[1] https://en.wikipedia.org/wiki/Sodium%E2%80%93sulfur_battery
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/
Recent formulations for sodium rechargeable batteries are room-temperature and non-flammable: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4525335/
Here's a a short article progress being made getting Na-ion batteries into an 18650 form-factor (their current prototype has an energy density of about 90 Wh/kg): https://news.cnrs.fr/articles/a-battery-revolution-in-motion
While energy density is lower than Li-ion, there's probably a good argument for longevity, safety, and material costs.
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 :)