As @YCor says in comments, there is a finitely generated example due to Ol'shanskii, which is essentially a kind of Tarski monster. However, Ol'shanskii's construction is very complicated. For "nicer" classes of groups, your question remains both important and open. As with most other kinds of Tarski monsters, I believe the answer to the following question remains unknown (though the answer is surely "yes").
Is there a non-free finitely presented group for which every proper subgroup is free?
Indeed, the question remains open even in very nice classes of groups.
Is there a non-free word-hyperbolic group in which every proper subgroup is free?
An example would be huge news, since it would resolve in the negative TWO famous open questions, viz:
Is every word-hyperbolic group residually finite?
and
Does every non-virtually-free hyperbolic group have a surface subgroup?
Since two big questions in one go seems like too much to hope for, I prefer to specialise to the case of subgroups of infinite index.
Is there a non-free, non-surface, infinite, word-hyperbolic group in which every proper, finitely generated subgroup of infinite index is free?
For this last question, there are examples outside of the world of hyperbolic groups. The solvable Baumslag–Solitar groups
$BS(1,n)=\mathbb{Z}[1/n]\rtimes_n\mathbb{Z}$
have the property that every nontrivial finitely generated subgroup of infinite index is infinite cyclic.