In Artin's "Algebra", he recommends proving this by "working with exponents, and use the description of the subgroups of (Z,+)." The recommended proof makes sense to me, but I have been unable to confirm if this alternative proof is also valid. Is it even possible to prove this fact without resorting to relative primality, Lagrange, or the first isomorphism theorem?
"Suppose a group (G,* ) is cyclic. Then there exists x in G such that (x)=G. Let H be a subset of G. Suppose that H is not cyclic. Then x is not a member of H, since otherwise (H,* )=(x)=(G,* ). So suppose that H is a proper subset of G.
Suppose that (G,* ) has other proper subgroups, and let F be a proper subset of G. That is, there exists y in G such that (y)=(F,* ). Since H is not cyclic, for all y in G such that (y)=(F,* ), H is not equal to F and y is not in H.
Suppose that (H,* ) is a group. For all x and y in G and with F a proper subset of G, either (x)=(G,* ) or (y)=(F,* ). If (H,* ) is a group then it is closed under the product. Closure implies that neither x or y are in H, since (H,* ) would cyclic in either case. So if (H,* ) is not cyclic, then it is not equal to G or a nonempty proper subset of G, so H is empty.
But if H is empty then (H,* ) is not a group, and so there is a contradiction with all of the suppositions. Therefore H must be cyclic."
After reading this a few times, I think one of the major problems (not already mentioned in the comments) can be found here:
In this excerpt -- specifically, the second sentence -- you are saying that just because $F \subset G$ proper, you can write $(F, *)$ as a cyclic group generated by some $y \in G$. But this assumption -- that a proper subgroup must be cyclic -- is exactly what you are trying to prove.
In fact, a subset $F$ of $G$ (inheriting the group operation from $G$) need not form a subgroup at all. And if it does form a subgroup, then (again) you cannot assume it'll be cyclic or you are simply assuming that which you've set out to prove.