It should be possible in theory to match the energy density of gasoline. You'd need to come up with a battery chemistry which takes in oxygen when it discharges and produces oxygen when it charges. Effectively, reversible combustion (or fuel cells). It's a tough problem but I don't think there's anything that fundamentally prevents it in theory.

Going much beyond it probably requires a nuclear process. You can store energy in certain isotopes by bombarding them with x-rays or gamma rays of a precise frequency. Stored energy can then be released with a similar process. In theory, it's possible to build a battery that uses this approach. In practice... to call it a difficult engineering problem would be a severe understatement.

Fundamentally, non-nuclear energy storage is limited by the strength of chemical bonds. For combustion, you're taking chemical bonds of high potential energy, breaking them apart, and rearranging the atoms into molecules with chemical bonds of lower potential energy. The energy difference is the heat produced by the combustion. The situation is similar in batteries, but in addition to rearranging atoms, free electrons are also liberated or consumed, with the bond energy difference going into that. For something like a mechanical spring, the winding force distorts the chemical bonds without breaking them, treating them like extremely tiny springs, with the same principle of operation as the big one. In all cases, the chemical bond strength determines how much potential energy can be crammed into the system.

For example, Wikipedia claims that flywheel energy storage (a "battery" where you just spin a disc faster to put energy in, and use it to drive something to get energy out) tops out at about 400Wh/kg. Lithium-ion batteries top out around 250Wh/kg, somewhat similar. Gasoline has a vastly better energy density at around 12,000Wh/kg... but gasoline needs to react with oxygen to release that energy! In fact it needs to react in an approximately 4:1 ratio, so the total mass going into the reaction is 5x the mass of the gasoline alone, making for an energy density of about 2400Wh/kg. Still much higher than batteries, but not outlandishly higher. I believe the difference would be because it's much easier to turn strong chemical bonds with a lot of potential energy into heat than it is to turn it into electrical potential.

You can see how reacting with the air gets you a huge advantage when it comes to how much stuff you need to carry around with you to store any given quantity of energy. And you can also sort of see how they all end up hitting the same basic limitations in the end. If you want to go further, you need take advantage of a stronger force with more potential energy, like the strong nuclear force.

(Gravity would be another possibility. If you could store energy by raising and lowering the orbit of a heavy object orbiting close to the Sun, you could get a pretty high energy density. Or if you want to go more exotic, store energy in the rotation of a neutron star or black hole. These approaches, however, pose even more difficulty for adaptation to automobile propulsion than the nuclear option.)

However, there's still plenty of room for improvement within that limit. In particular:

1. The best batteries are still quite a bit below the energy density of gasoline+oxygen.

2. Creating batteries that can use stuff in the air the way gas engines do can let you "cheat" the energy density numbers.

3. There's a lot of room for improvements to how much batteries cost for any given capacity.

4. Similarly, there's a lot of room for improvements in battery longevity, in terms of how many charge cycles it can handle before it loses capacity.

5. Again similarly, there's a lot of room for improvement in charging speed.

I think 3-5 are key. Energy per mass or energy per volume is good enough for many applications now. It's not enough for airplanes yet, but as Tesla has shown, it's good enough for practical cars. The battery pack in a Model S is pretty heavy, but the fact that the rest of the drivetrain is so compact compensates a lot. The result is still heavier than a normal car, but not excessively so. The real limitations for electric cars are high cost (which is why the Tesla costs $70,000 and up, and cheaper electric cars have terrible range), battery replacement after some years of use (really just another dimension of cost), and slow charging speeds (meaning you have to wait 30 minutes or more for a charge, which is fine for normal city driving when you charge at home overnight, but troublesome for people who can't charge at home, or who are on a road trip).

I'm not aware of any fundamental physical limitations at play in those areas yet, and at this point they're probably more important than raw energy density.