The proof of Zeeman described in this note is by a substantial margin the easiest and most conceptual proof I know. To simplify the exposition I restrict to orientable surfaces in the note, but it is trivial to also do the non-orientable case (and see the edit below for one description of how to arrange this to avoid using the fact that three cross caps is a handle plus a cross cap).
What I particularly like about it is that it proves not only that the usual classification is the complete list of surfaces, but also at the same time that the Euler characteristic is a complete invariant of orientable surfaces. Indeed, the proof is by (descending) induction on the Euler characteristic, with the base case the 2d Poincare conjecture: all compact connected surfaces have Euler characteristic <=2, with equality iff the surface is a sphere (and you can see the sphere very clearly in the proof, which directly produces from equality a decomposition of the surface into two discs meeting along their boundary).
As evidence of how simple this proof is, on many occasions I have explained it at a chalk board (with full details) in about 10 minutes.
EDIT: I've thought a little bit more about whether or not you can avoid having to prove that the connect sum of $3$ projective planes is isomorphic to the connect sum of a torus and a projective plane. Here is one way to arrange the proof that avoids directly proving this.
As in the proof in my notes, you prove the theorem by downward induction on the Euler characteristic. More precisely, what you prove by induction is the following:
Every connected surface has Euler characteristic less than or equal to $2$.
If a surface is orientable, then its Euler characteristic is even and if it equals $2-2g$, then the surface is a connect sum of $g$ tori.
If a surface is not orientable and if its Euler characteristic is $2-g$, then the surface is a connect sum of $g$ projective planes.
Notice that this implies as a consequence that the connect sum of $3$ projective planes is isomorphic to the connect sum of a torus and a projective plane (which will not be used directly in its proof).
Anyway, you follow the proof in my notes to deal with the base case (which combines $1$ above and the fact that the sphere is the only connected surface of Euler characteristic $2$). You then follow my notes in the inductive case to the point where you find the nonseparating simple closed curve $\gamma$. There are then several cases:
a. If your surface is orientable, then $\gamma$ is a $2$-sided curve, so you can cut and cap off to increase the Euler characteristic by $2$, and be done by induction.
b. If your surface is nonorientable and $\gamma$ is a $1$-sided curve such that cutting along $\gamma$ gives a nonorientable surface, then you can do just like in a (but cutting along $\gamma$ and capping only increases the Euler characteristic by $1$).
b. If your surface is nonorientable and $\gamma$ is a $1$-sided curve such that cutting along $\gamma$ gives an orientable surface, then you can cut cap and induct and deduce that your surface is isomorphic to $\Sigma_g \# \mathbb{P}^1$ for some $g \geq 1$. Of course, this is not what you want; however, if you draw the picture you can easily find a simple closed $1$-sided curve $\gamma'$ on $\Sigma_g \# \mathbb{P}^1$ such that cutting along $\gamma'$ gives a nonorientable surface. This is the curve you should have been using all along! Replace $\gamma$ with $\gamma'$, and go back to case b.
d. Finally, if your surface is nonorientable and $\gamma$ is a $2$-sided curve, then the complement of $\gamma$ must be nonorientable, so cutting and capping we find that the surface must be isomorphic to $\Sigma_1 \# (\#_{k} \mathbb{P}^1)$ for some $k$. Just like in case c, we can find a $\gamma'$ that is $1$-sided such that the complement is nonorientable, and then go back and use that one in case b.