One approach is the following: Let $M = M_{2}(\mathbb{Q}).$ Note that if $x$ is an element of order $4$ or $3$ in $G,$ then the subalgebra $C_{M}(x)$ is a division ring by Schur's Lemma, as $x$ acts irreducibly. Hence $C_{G}(x)$ is cyclic. In particular, Sylow $3$-subgroup of $G$ is cyclic, of order $3$ as you have shown already. Let $S$ be a Sylow $2$-subgroup of $G,$ and let $A$ be a maximal Abelian normal subgroup of $S$. If $A$ has exponent $2,$ then $A$ is elementary Abelian, and hence has order at most $4.$ Otherwise, $A$ contains an element $x$ of order $4,$ and then $A$ is cyclic as $C_{G}(x)$ is cyclic. Also, as you have shown, $|A| \leq 4$ in that case. Now as $A$ is maximal Abelian normal in $S,$ we have $C_{S}(A) = A,$ and $S/A$ is isomorphic to a subgroup of ${\rm Aut}(A).$ If $A$ is a Klein $4$-group, then ${\rm Aut}(A) \cong S_{3}$ and if $A$ is cyclic of order $,$ then ${\rm Aut}(A)$ has order $2.$ Hence in either case, $|S| \leq 8.$ Since you have already ruled out a quaternion group of order $8,$ the only possibility if $S$ is non-Abelian of order $8$ is that it is dihedral ( and we already know that if $|S| = 8,$ it is non-Abelian).
By the way, you can't rule out all non-Abelian group of order $12,$ since a dihedral group with $12$ elements does occur.
I don't know how much group theory you know, but I would finish as follows: let $F = F(G),$ the Fitting subgroup of $G.$ If $F$ contains an element of order $3$ or then $C_{G}(F) = F$ is cyclic of order $3$ or $6$ (for $F$ contains a central element of order $3$ in that case). Then $G/F$ has order dividing $2$. I won't give all details, but if $|G/F| =2,$ that leads to $G$ dihedral with $6$ or $12$ elements ($G=F$ leads to $G$ cyclic of order $3$ or $6$ in this case).
There remains the case that $F$ is a $2$-group. If $F$ is Abelian , we have $F$ cyclic of order $4$ or a Klein $4$-group. The first possibility leads to $G = F.$ The second also leads to $G = F,$ eg by Clifford's theorem. there can be no element of order $3$ in $G$ in that case. If $F$ is non-Abelian of order $8,$ then we must also have $G = F$, because a dihedral group of order $8$ has no automorphism of order $3.$
Most proofs of the Nielsen-Schreier theorem proceed by following a recipe for finding generators of the subgroup $H$ in $F$ and then proving that they are free generators.
You start by finding a (right) Schreier (= prefix closed) transversal of $H$ in $F$. Let $X$ be a set of free generators of $F$ and, for $g \in F$, let $\bar{g}$ denote the unique element of $U$ with $Hg = H\bar{g}$.
Then the subset of non-identity elements of the set $$\{ux \overline{ux}^{-1} : u \in U, x \in X \}$$
freely generates $H$.
In your example, we can take $U = \{1,a\}$, leading to the free generating set $\{b,a^2,aba^{-1}\}$ of $H$, which is the same as that found in the answer by kabenyuk.
You can check normality of a subgroup $H$ of $F$ by constructing the permutation representation of $F$ on the cosets of $H$ in $F$, and then checking whether the generators of $H$ all act trivially on this set.
The above method of testing for normality is fine for subgroups of moderately small finite index, but for arbitrary finitely generated subgroups, you can use the fact that membership testing in such subgroups is possible (using methods based on Stallings' Folding) and then testing membership of $xgx^{-1}$ and $x^{-1}gx$ in $H$ for all $x \in X$ and generators $g$ of $H$.
Best Answer
Let $G = \langle x,y \mid x^2,y^3 \rangle \cong {\rm PSL}(2,\mathbb{Z})$.
Question 1. Yes. Let $H < G$, and consider the permutation action of $G$ on the (left or right) cosets of $H$ in $G$. If $|G:H| < 6$, then it is not possible for the images of both $x$ and $y$ to act fixed point freely, and so $H$ contains a conjugate of $x$ or $y$ and hence cannot be free.
Question 2. No, but the two subgroups that you have found are the only two normal subgroups of index $6$ in $G$. You can see this by observing that there is essentially only one surjective group homomorphism from $G$ to each of $C_6$ and $S_3$ (i.e. up to equivalence under an automorphism of $C_6$ or $S_3$), so there are only two possible kernels $H$.
By a computer calculation, I found that there is also one conjugacy class of non-normal subgroups $H$ with $|G:H| = 6$ and with $H$ free of rank $2$, and a representative of this class is $H=\langle yx, y^{-1}(xy)^3 \rangle$. The quotient of $G$ by the core of $H$ is isomorphic to $S_4$, and there are three conjugates of $H$ in $G$.
Question 3. I can only say here that the reason is that we have a proof that this is the case!
Note that the Kurosh Subgroup Theorem says that any subgroup of $G$ is a free product of conjugates of $\langle x \rangle$, $\langle y \rangle$ and a free subgroup of $G$. So, for $H \lhd G$, if $H$ does not contain $x$ or $y$, then it must be free. I believe that the rank of free subgroups of free products can be calculated using Euler Characteristics, but I don't know the details.