What is tricky about proving the Nielsen–Schreier theorem?

But then this is also a nontrivial relation in $F$

This step is not obvious at all. To get a nontrivial relation in $F$, you need to know that when you expand $h_1,\dots,h_n$ in terms of the free generators of $F$, then $h_1\dots h_n$ reduces to a nontrivial reduced word. Why should that be true?

Indeed, it may not be true. You have glossed over the fact that you need to choose some specific subset of $H$ which will be your free generators. If you choose incorrectly, then there will be nontrivial relations. For instance, suppose $F$ is free on generators $a$ and $b$, and you take $H$ to be the subgroup generated by $h_1=ab$, $h_2=aba$, $h_3=bab$. Then $h_1^3h_3^{-1}h_2^{-1}=1$ is a nontrivial relation among these generators of $H$ (but when you expand this out in terms of the generators of $F$, it reduces to the trivial word, so this does not contradict freeness of $F$). So $H$ is not freely generated by $\{h_1,h_2,h_3\}$. To prove $H$ is freely generated, you have to somehow come up with a special set of generators for which there will be no nontrivial relations.

Now for this particular $H$, that is not so hard (in fact, $H$ is all of $F$, so you can take $a$ and $b$ as your free generators). But if you have some completely arbitrary subgroup of $F$, it is not at all obvious how you would come up with a generating set such that any relation between them would still be a nontrivial relation in terms of the free generators of $F$, thus giving a contradiction as you suggest.