This is not really an answer, but not really a comment either.
You can start from the classification theorem of compact surfaces (every compact connected 2-manifold is homeomorphic to either a connected sum of $g$ tori or a connected sum of $k$ projective planes, with a finite number of disks removed). To prove this you need the triangulation theorem, which is proved in Moise's Geometric Topology in Dimensions 2 and 3, and once you have a triangulation you can prove by hand that you will always get a connected sum of tori or projective planes.
After that, you can prove the result you want by hand by drawing nice pictures :)