The first explanation provides the mathematically rigorous reason that the charge can only reside on the surface, while the second one is supposed to give you the right physical intuition. (You criticize it for being hand wavy—which it is—but a "physical and intuitive explanation, rather than a strictly mathematical one" is, of necessity, going to involve some hand waving.)
If you understand why the electric field has to be zero inside a conductor at equilibrium (for if it were nonzero, the free charges inside would be accelerated, and you would not be in equilibrium), then it is actually easy to get that the net charge anywhere in the interior is also vanishing. The connection comes through Gauss's Law. The differential form of Gauss's Law states that $\vec{\nabla}\cdot\vec{E}=\rho/\epsilon_{0}$ (in MKS units, but the units are not important here). If the electric field $\vec{E}$ is zero, then so is its divergence, and thus so is the charge density $\rho$. Thus, the net charge in the interior of a conductor has to vanish.
By process of elimination, if there is a net charge on a conductor, and it does not lie in the interior, it must lie on the surface. At the surface, the charges are not completely free to move (that literally defines where the surface of the conductor is located), so the preceding argument that there could be no net charge present does not apply. (Note, however, that while charges are not free to move beyond the surface, they are free to move parallel to, and just inside, the surface; this means that the the electric field parallel to the surface of a conductor also vanishes, just like the full field in the interior.) Both interior and exterior surfaces of a conductor are thus allowed to carry charge, although interior surfaces (surrounding cysts of vacuum or insulating material) only will carry net charge if there is a free charge located inside the hole.
That the like charges repel each other, pushing all of them to the surface to minimize the total potential energy is true, and that description is designed to give you a physical intuition for what is going on. However, you are correct that proving that the minimum-energy configuration has all the charges pushed to the boundary is mathematically nontrivial. In fact, the easiest way to prove demonstrate this fact is to use the argument I outlined in the preceding paragraphs, showing that the charge is located on the surface under equilibrium conditions. It is also possible to set up an integral expression for the energy of an arbitrary charge distribution over the surface and interior of the conductor and to use the calculus of variations to show that the minimum energy configuration has all the charge located on the boundary, but that is a much trickier way to approach the problem.
