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".