The energy is stored in the magnetic field. I usually think of it as "magnetic field lines repel" but that is not very precise (useful for intuition though).
But along the same lines as your capacitor example (moving the plates to infinity takes work), if you look at a simple current loop there is a force on the wires from the magnetic field generated. This force is repulsive: the loop would like to get bigger. If you could slowly "grow" the loop, you could do work in this way. And the amount of work done is once again equal to the energy stored. Just like for capacitors.
I deliberately stayed away from equations - hoping this verbal picture helps your understanding.
Wouldn't this inductor's emf counteract the discharging capacitor and actually charge it? / stop the capacitor from fully discharging?
The inductor doesn't care about what the charge state of the capacitor is. All it cares about is how quickly the current through it is changing, and it generates a back-voltage according to the equation V=L*dI/dt. You can think of an inductor as giving "momentum" to the current. If the current is zero, then it wants to keep the current zero. If the current is non-zero, it wants to keep the current at that same non-zero value. If the current is increasing, it generates a counter-voltage acting in the opposite direction to the current flow.
The analogy I like to use is a circuit of water pipes in which inductors are represented by a heavy propellor in a water pipe. If water flow is suddenly turned on, the heavy propellor initially resists the flow of water. But over time the propellor spins faster in response to the water flow. If the water flow past the propellor is then reduced, the heavy propellor resists the decrease in water flow because it is now spinning fast and tries to continue pushing the water through the pipe. This is analogous to how an inductor resists changes in the electrical current flow through it.
Using this water circuit analogy, a capacitor can be represented as a section of pipe which has a rubber membrane stretched across the inside of it. If you push water into one end of this pipe section, the rubber membrane stretches and creates a back pressure resisting attempts to push more and more water into it. If you then stop applying water pressure to that side of the pipe section, the rubber membrane springs back to its flat, equilibrium position, pushing the water back out the same side of the pipe as you were trying to push the water in. This is analogous to how a capacitor "pushes back" with a back-voltage when you push electrical charge into a capacitor.
If you make a closed electrical circuit with this heavy propellor (which represents the inductor) and the rubber-membrane pipe section (which represents the capacitor), then you should be able to see how a resonant water oscillation in the circuit can be set up. Imagine the rubber membrane pipe section being "charged" by forcing water into one side. When you release the applied pressure, water will flow past the heavy propellor, which will then speed up and try to maintain a constant water flow past it. However, as the water flows past the heavy propellor and into the other side of the rubber membrane pipe section, the rubber membrane goes to its equilibrium position and then starts getting stretched in the opposite direction. Eventually, the back-pressure becomes so large that the direction of water flow is reversed and the cycle happens all over again.
In summary, with this analogy we have the following:
electrical current <-> water flow
voltage <-> water pressure
inductor <-> heavy propellor
capacitor <-> rubber membrane pipe section
Hopefully, visualizing things this way can give you an intuitive grasp of how a capacitor and inductor work together to form a resonant circuit.
Best Answer
It is not true that "potential difference makes no sense when the curl of $\vec E$ is nonzero". Instead, the scalar and vector potentials $\Phi,\vec A$ may always be defined and the electric field may be expressed in terms of these variables as $$ E = -\nabla \phi - \frac{\partial A}{\partial t} $$ In fact, these potentials aren't unique – any other choice of the potentials related to the original one by a gauge transformation is equally good to calculate the same $\vec E$ and $\vec B = \text{curl }\vec A$.
In an rlc circuit, one may always confine the nonzero $\vec A$ to a small vicinity of the inductor which also determines the right gauge transformation. Then the potential difference across any element of the circuit is well-defined and the sum of these differences over a closed loop is zero.