I would like to prove the following:
Let $M$ be a non-finitely generated right module over a ring $R$, and presume axiom of choice is true. Then there exists a subset of $M$, such that it generates $M$, and it's minimal as far as subsets that generate $M$ go.
The discussion that follows in the comments in the link above didn't clear up much, as it seemed too advanced for me. Also I'm not too interested in whether full choice is needed etc., I'm fine with presuming full choice.
Here's what I've done so far. The idea is we use Zorn's lemma on subsets of linearly independent elements. We get a maximal element, a subset $A$ of independent elements. If we could show that this subset generates the whole module, we would be done, because any proper subset would not generate the whole module (if that were not true, we would get a contradiction with independence of $A$).
However, I don't know how to show that $A$ actually generates the whole module. Presuming it's not, if we take some element $c$ that's not in $A$, it doesn't seem like I can simply add $c$ to $A$ (in hopes of getting a contradiction with maximality of $A$), because I don't really know that $cR \cap A=0$.
This isn't true without some additional hypotheses. For instance, if $R=\mathbb{Z}$ and $p$ is a prime, the module $\mathbb{Z}[1/p]/\mathbb{Z}$ has no minimal generating set (a generating set must contain elements of order $p^n$ for arbitrarily large $n$, but an element of order $p^n$ generates the entire submodule of elements of order $\leq p^n$ and thus any individual generator is redundant).
On the other hand, it is true if $R$ is commutative and artinian. Suppose $R$ is commutative and artinian and let $M$ be any $R$-module. Then $M$ is equal to the direct sum of its localizations at each of the finitely many primes of $R$, so by considering each direct summand separately we may assume $R$ is local with maximal ideal $p$. Choose a basis for $M/pM$ over $R/p$ and lift it to a set $B$ of elements of $M$. Clearly no proper subset of $B$ can generate $M$ (since it does not generate $M/pM$), so it suffices to show that $B$ generates $M$.
Let $N\subseteq M$ be the submodule generated by $B$. Since $B$ generates $M/pM$, we have $N+pM=M$. But then we get $$M=N+pM=N+p(N+pM)=N+p^2M=N+p^2(N+pM)=N+p^3M$$ and so on by induction. Thus for all $n$, $M=N+p^nM$. But since $R$ is artinian, $p^n=0$ for $n$ sufficiently large. For such $n$ we have $$M=N+p^nM=N+0=N.$$ That is, $B$ generates $M$.
While the context of the linked discussion was modules over a commutative artinian ring, I doubt this is the argument Tobias Kildetoft had in mind when he commented that "the existence of such a minimal generating set in general can be obtained from Zorn's lemma in a similar way to the one for vector spaces". I'm guessing he instead had an erroneous argument that involved taking a maximal irredundant set of generators (i.e., a set of elements such that if you remove any one, it generates a smaller submodule). The problem with this argument is that there is no reason such a maximal set has to actually generate the whole module. You might think you can always add one more generator if you don't have the whole module, but adding one more generator might make some of your previous generators redundant.