Well order the generators of G and their inverses. (Yes, we're using choice, but I think you can get away without it if the generators of G are countable.) Thus the generators of G are a0 a1 a2 a3, and so on.
Order the words of G by length, then lexicographically.
Let bi be the minimum word in the ith right coset of H. This will be the canonical representative for that coset. Notice that e represents H.
Our system of cosreps is closed under left substrings. To illustrate, let b3 represent the third coset of H in G, and assume b1u = b3. We're talking specifically about concatenation here; there is no cancellation. The first part of b3 is b1, and the second part is u.
If b1 and b3 represent the same coset then we should have selected b1 in the first place. Thus b1 represents a new coset of H.
Suppose w lies in H, and wb1 is smaller than b1. This time juxtaposition means group multiplication; so cancellation is possible. The product wb1 is either shorter, or it is the same length and begins with an earlier letter. Bring in u, and if there is no cancellation, wb1u is shorter, or has the same length and begins with an earlier letter. If cancellation occurs (because w has swallowed all of b1 and part of u), then the string is shorter still. Thus wb3 is a lesser representative for the third coset, and that is a contradiction.
Every left substring of a cosrep bi is some other cosrep bj.
Use schreier nielsen rewriting to create a set of generators for H. A typical generator is biaj/bk, where bk brings the element back into H. This three part word cannot be reduced. Suppose bi ends with the inverse of aj, thus permitting cancellation. The result is a left substring, which is some other cosrep, say bk. To bring this back into H, we divide by bk. The result is e, the trivial generator. These can be left on the cuttingroom floor.
Suppose bk ends in aj, so that aj gets eaten by the inverse of bk on the right. Let w equal bk with aj removed. Thus bi/w lies in H. Multiply by w on the right and bi and w represent the same coset of H. Since w is a left substring, it is the canonical cosrep, as is bi. Therefore w = bi, and once again the generator collapses to e, and can be ignored.
If a schreier generator biaj/bk survives, it cannot be reduced.
The schreier generators produce a free group that maps onto H. If none of the words produced by these generators collapses to e, then the homomorphism is a monomorphism, and H is free. In other words, the subgroup of a free group is free. We only need to prove the reduced concatenation of schreier generators does not drop to e.
The heart of each schreier generator is the letter aj in the middle. These letters never go away, hence the string never drops down to e. For notational convenience, I'm going to use numbers for indexes. I don't feel like coming up with six more letters.
Consider the adjacent schreier generators b1a2/b3 * b4a5/b6.
Suppose b3 = b4, hence they cancel each other exactly. If a2 and a5 are inverses, then b1/b6 lies in H. Both represent the same coset of H, and b1 = b6. The two schreier generators were inverses, and the word, written in schreier generators, was not reduced. This is a contradiction, hence b3 ≠ b4. (This same logic applies even if b3 and b4 are empty.)
Next suppose 1/b3 eats b4 and a5 (and perhaps part of b6 as well). Now b4a5 is a left substring of b3. This becomes a cosrep, in the same coset as b6, and equal to b6. That makes b4a5/b6 a trivial generator - not part of H.
Finally, suppose a2/b3 is eaten by b4 on the right. This makes b3/a2 a cosrep, equal to b1, and b1a2/b3 goes away.
None of the central elements cancel, a schreier word never becomes empty, the map from a free group onto H is injective, and H is free.