Positive genus Fuchsian groups

Yes, this is true, but proving this is easier than finding a reference.

1. Every finitely-generated matrix group (e.g. a lattice in $PSL(2, {\mathbb R})$ contains a torsion-free subgroup. The general result is due to Selberg, but for discrete subgroups of $PSL(2, {\mathbb R})$ it was surely known earlier.

2. In view of 1, it suffices to prove that every surface $S$ homeomorphic to the 2-dimensional sphere with $n\ge 3$ punctures admits a finite covering $S'\to S$ such that $S'$ has positive genus. Suppose first that $n$ is odd. Surround punctures $p_i$ by small loops $c_i$. I will think of these as elements of $H_1(S, {\mathbb Z}_2)$. Now, consider the homomorphism $$ \alpha: \pi_1(S)\to H_1(S, {\mathbb Z}_2)\to {\mathbb Z}_2$$ where the first arrow is Hurewicz and the second sends $[c_1], [c_2]$ to $1$ and the rest of $[c_i]$'s to $0$. Take the 2-fold covering $S_1\to S$ corresponding to the kernel of $\alpha$. Then $S_1$ is $2+ 2(n-2)$-times punctured sphere. Thus, the problem is reduced to the case of spheres with even number of punctures.

3. Let $S$ be $S^2$ with $n=2k\ge 4$ punctures. Similarly to (2), define the homomorphism $$ \beta: \pi_1(S)\to H_1(S, {\mathbb Z}_2)\to {\mathbb Z}_2 $$
   where the second arrow sends all $[c]_i$'s to the nonzero element of ${\mathbb Z}_2$. Let $S'\to S$ denote the 2-fold covering corresponding to the kernel of $\beta$. Then $S'$ will have $2k$ punctures and genus $k-1>0$. (This is an exercise in topology of surfaces. The natural extension of $S'\to S$ to a ramified covering of compact surfaces is called a hyperelliptic covering map.)

Edit. 1. If you want a reference, an optimal result is in

Edmonds, Allan L.; Ewing, John H.; Kulkarni, Ravi S., Torsion free subgroups of Fuchsian groups and tessellations of surfaces, Invent. Math. 69, 331-346 (1982). ZBL0498.20033.

It can be stated as: Suppose that $F_1, F_2$ are lattices in $G=PSL(2, {\mathbb R})$. Then $F_2$ embeds in $F_1$ (as an abstract group) with index $k$ if and only if the Riemann-Hurwitz condition is satisfied: $$ \chi(F_2)/\chi(F_1)=k. $$
Once you unravel the definitions, it implies the positive answer to the positive genus question.

2. In order to apply their result, one needs to know (and they take it for granted) that every lattice in $G$ has the presentation $$ \langle a_1, b_1,...,a_p, b_p, c_1,...,c_r, d_1, ..., d_s| \prod_{i=1}^p [a_i, b_i] \prod_{j=1}^rc_i \prod_{k=1}^s d_k =1, c_1^{e_1}=...=c_s^{e_s}=1\rangle. $$ This presentation one can find in Poincare's papers on Fuchsian functions. Whether he actually had a proof is hard to tell (this applies to pretty much everything written by Poincare that I tried to read, but others might disagree), but he had a tool for proving the result, namely convex fundamental domains. A more solid proof is likely to be found in Dehn's papers (I did not try). The earliest solid reference I know for the existence of a finite generating set for lattices $\Gamma< G=PSL(2, {\mathbb R})$ is

Siegel, Carl Ludwig, Some remarks on discontinuous groups, Ann. Math. (2) 46, 708-718 (1945). ZBL0061.04505.

Unsurprisingly, Siegel uses fundamental polygons to prove the result: He proves the existence of a finitely-sided fundamental polygon and, as a consequence, concluded an explicit upper bound on the number of generators in terms of the area of the quotient ${\mathbb H}^2/\Gamma$. This finiteness theorem holds in much greater generality, for lattices in connected Lie groups, but this is another story (that also has complicated history to the point that it is unclear whom to credit with this, clearly fundamental, result). One thing, that I am not sure about is:

While the existence of finite generating sets for lattices in connected Lie groups is known, I do not know a solid reference to an explicit upper bound on the number of generators in terms of the volume of the quotient (in the non-torsion free case).

3. Regarding "Fenchel's Conjecture" that each lattice in $G=PSL(2, {\mathbb R})$ contains a torsion-free subgroup of finite index: The story is somewhat bizarre. When the conjecture was first stated is hard/impossible to tell. It is mentioned in Nielsen's paper

J. Nielsen, Kommutatorgruppen for det frie produkt af cykliske grupper, Matematisk Tidsskrift. B (1948), pp. 49-56.

Nielsen's paper, remarkably, contains no references whatsoever.

However, by the time of appearance of Nielsen's paper, Fenchel's conjecture was already proven. The proof is mostly contained in:

Mal’tsev, A. I., On the faithful representation of infinite groups by matrices, Am. Math. Soc., Transl., II. Ser. 45, 1-18 (1965); translation from Mat. Sb., N. Ser. 8 (50), 405-422 (1940). ZBL0158.02905.

Now, each lattice $\Gamma< G=PSL(2, {\mathbb R})$ is finitely generated and contains only finitely many $\Gamma$-conjugacy classes of finite order elements. (This, at the very least, comes from Siegel's theorem on fundamental polygons which, as I said, was likely to have been known to Poincare.) Mal'tsev's theorem implies that if $\Gamma$ is a finitely-generated matrix group, then for every finite collection of nontrivial $\Gamma$-conjugacy classes $C_1,...,C_k$, there exists a finite-index subgroup $\Gamma'< \Gamma$ disjoint from $C_1,...,C_k$. By combining the two results, every lattice in $G=PSL(2, {\mathbb R})$ contains a torsion-free subgroup of finite index.

A complete solution of Fenchel's conjecture was claimed by Fox in

Fox, Ralph H., On Fenchel’s conjecture about (F)-groups, Mat. Tidsskr. B 1952, 61-65 (1952). ZBL0049.15404.

who was clearly unaware of Mal'tsev's paper. Fox's solution turned out to be partially erroneous, with an error (in one of the cases) corrected in:

Chau, T. C., A note concerning Fox’s paper on Fenchel’s conjecture, Proc. Am. Math. Soc. 88, 584-586 (1983). ZBL0497.20035.

By that time (23 years earlier), Selberg proved an even more general result in:

Selberg, Atle, On discontinuous groups in higher-dimensional symmetric spaces, Contrib. Function Theory, Int. Colloqu. Bombay, Jan. 1960, 147-164 (1960). ZBL0201.36603.

Selberg proved that each finitely-generated matrix group contains a torsion-free subgroup of finite index. Selberg was also unaware of Mal'tsev's paper but, at least he was not reporoving something which was already there. The thing is that a finitely generated matrix group $\Gamma$ can have infinitely many $\Gamma$-conjugacy classes of finite subgroups, hence, one cannot simply apply Mal'tsev's result.