Is it possible to construct (without choice, even?) a non-finitely-generated group with no proper non-finitely-generated subgroup? Is there a non-finitely-generated group each of whose proper subgroups is finitely generated? If so, what form of choice (if any) is required to construct such a group?
 A: (CW since this is just expanding on George Lowther’s comment to the question, which could really have been an answer in the first place; if George L wants to convert his answer to a comment himself, I can delete this one.)
For any prime $p$, the Prüfer $p$-group is as desired.
There are several constructions of this; a good one for present purposes is
$$\mathbb{Z}[1/p]\ /\ \mathbb{Z}$$
i.e. rationals with denominator a power of $p$, modulo the integers.
To see that this works, note that it is the union of the linearly ordered chain of finitely generated (indeed, cyclic) subgroups $H_i := \{ [a / p^i]\ |\ 0 \leq a < p^i \}$, over $i \in \mathbb{N}$.
Now any element of $H_{i+1}$ not in $H_{i}$ must be of the form $[a/p^{i+1}]$ with $a$ coprime to $p$, and hence generates the whole of $H_{i+1}$.  So any subgroup is either equal to some $H_i$, or else contains them all and is the whole group.
On the other hand, the entire group is clearly not finitely generated since any finite set of elements is contained in some $H_i$.
