This model is something that I've seen a lot of students (including myself) struggle with, and a big part of it is that calling it the "Coulomb barrier" is quite over-simplified.
Going back to fundamental physics principles, the Coulomb force is repulsive as you say, so I'll write this as $F\propto 1/r^2$, where $F$ is the force and $r$ is the distance from the center of the nucleus and the positive sign indicates that the force is in the positive $r$ direction, away from the nucleus. The potential, which is what's shown on the graph, is the negative of the integral of the field (which is proportional to the force), this results in $E\propto 1/r$. For an analog, imagine lifting a weight where "up" is the positive z-axis. The path involves an increase in z-coordinate and the force from the field (gravitational) is negative. The negative integral of the field over distance is the potential.
The missing part is why they "chop off" this $1/r$ function at some radius, presumably the radius of the nucleus. Well, this allows us to infer some things about the other force present, which is the nuclear force. It would appear that the force acts weakly beyond the radius of the nucleus, since the $1/r$ form is unaltered beyond that point. It also absolutely must have a potential that increases faster than $1/r$ as $r \rightarrow 0$. Both of these would be loosely satisfied if the nuclear potential was $-1/r^n$ (note the negative) where $n>1$. The alpha particle, while in the nucleus, by the way, has kinetic energy which is the reason its energy is higher than the hypothetically lowest energy level possible for it. This has to do with the fact that quantum mechanics only allows certain (quantized) energy levels.
Just For an example of how this is possible, I'll say $E_{nuclear}=-1/r^4$ (I am not saying this is how the force acts, it's just for utility).
$$E(r) = E_{nuclear}(r) + E_{Coulomb}(r)$$
$$E(r) = 1/r - 1/r^4$$
$$F(r) = -\frac{d}{dr} \left( E_{nuclear}(r) + E_{Coulomb}(r) \right) = F_{nuclear}(r) + F_{Coulomb}(r) $$
$$F(r) = 1/r^2 - 1/r^5$$
My intent is that this answer allows you to explicitly answer to yourself what the potential and force contributions are, and give some very rudimentary example for how the "edge" can appear. Beyond that I hope it's clear how someone may take the shape of the above curve and lump it into a "wall".
The energy does not change. The quantum mechanical solution of the potential problem with a barrier is such that it gives a probability for each specific energy level to go through the barrier .
In this explanation one sees a free particle reaching the barrier, and how the probabilities change, but not the energy:
Thus no extra energy is needed, but a lot of patience :) , because the probabilities are small usually and either one has to study a large number of the same conditions, or be in wait for the phenomenon.
Tunneling has been used to evaluate nuclear decays, for example the Polonium alpha decay lifetime :
Best Answer
Classically the answer on this question was depending on your favorite interpretation of quantum mechanics, anyway now in the framework of Quantum field theory and quantum electrodynamics, we can say that this "extra energy" comes from vacuum, because we now know (but to be very precises not 100% sure yet) that vacuum not that empty thing, and it is fluctuate continuously, and this fluctuations makes very small input on various process that happens in quantum word, anyway this input makes such a very interesting phenomenons as this energy borrowing you mentioned.
Anyway one should emphasize that the energy is really "borrowed" in sense that it should be "returned back", for this we say that average vacuum expectation value is always zero.