Take the proof that any compact smooth manifold admits triangulations, and set the dimension to two. 

The idea goes like this:

* Embed your surface (or $n$-manifold) in $\mathbb R^5$ ($\mathbb R^{2n+1}$ in general).  

* Triangulate $\mathbb R^5$, and make the surface transverse to the triangulation.  If the surface does not intersect each simplex in a locally linear manner, subdivide the triangulation and repeat this step until it does. 

* The pull-back of the triangulation to the surface is a decomposition into convex polyhedra.   A subdivision turns this into a triangulation. 

Paraphrasing Allen Hatcher:

If you're interested in topological surfaces, the paper

 A.J.S. Hamilton, The triangulation of 3-manifolds, Oxford Quart. J. Math. 27 (1976), 63-70

takes the Kirby-Siebenmann machinery and scales it down to 3 dimensions where it becomes somewhat simpler, so one can prove existence and uniqueness of triangulations of 3-manifolds using only standard PL techniques, such as results of Waldhausen.  Presumably the same approach would work for surfaces.  Since the method works in 3 dimensions it can't be using the topological Shoenflies theorem since this fails in 3 dimensions.  On the other hand, it would use some PL (or smooth) surface theory so it wouldn't be entirely "from scratch".

edit: Allen wrote this argument up in a recent paper.  See this thread for details http://mathoverflow.net/a/151760/353