If each strict subgroup of a group G is free, must G be free or cyclic of prime order ?

No. There is a variation of Tarski monster: a nonabelian group whose each proper nontrivial subgroup is infinite cyclic, see the book of Olshanskii. Concerning Misha's comment. For any countable family of countable involutionfree groups $G_1,G_2,\dots$, there is a group $H$ containing all $G_i$ as proper subgroups such that each proper subgroup of $H$ is either infinite cyclic or a conjugate of a subgroup of some $G_i$. This is Obraztsov's embedding theorem. 

