I'm not sure what ingredients you are allowing, but here is one proof sketch:
Let $A$ be our f.g. abelian group. Since $\mathbb Z$ is Noetherian, the torsion subgroup $A_{tors}$ is also f.g., and the quotient $A/A_{tors}$ is torsion free, and f.g. (being a quotient of something f.g.). [As pointed out in a comment, we will later show that $A_{tors}$ is a direct summand of $A$, and so the Noetherianess argument is not actually needed.]
(1) If $A$ is f.g. and torsion free over $Z$, it is free.
Proof: Induction on the dimension of $V := {\mathbb Q}\otimes_{\mathbb Z} A$ (which is fin. dimensional, since $A$ is f.g.).
If this equals $1$, then $A$ is a f.g. subgroup of $\mathbb Q$, and finding a common denominator shows that it is cyclic. (This is the Euclidean algorithm.)
In general, choose a line $L$ in $V$. If $A \cap L = 0$, then $A$ embeds into $V/L$, the dimension drops, and we are done by induction. (Of course, this actually can't happen, but never mind; we don't need to prove that here.)
Otherwise, we have $0 \rightarrow A/A\cap A\cap L \rightarrow A \rightarrow B \rightarrow 0,$ and $B$ embeds into $V/L$, so is free by induction, $A/A\cap L$ is f.g. (by Noetherianess of $\mathbb Z$) and embeds into $L$, so is free by the dim. 1 case. Freeness of $B$ makes this s.e.s split, so $A = A\cap L \oplus B$ is free.
(2) In general, $A = A_{tors} \oplus \text{something free} .$
Proof: We have the s.e.s $0 \rightarrow A_{tors} \rightarrow A \rightarrow A/A_{tors} \rightarrow 0.$ Part (1) shows that $A/A_{tors}$ is free, and then this freeness lets us split the s.e.s.
(3) Now suppose $A$ is torsion. Its Sylow subgroups are unique (by abelianess, although there are many other ways to prove this too), and all have mutually trivial intersections, to $A$ is isomorphic to their direct sum.
(4) We have now reduced to the case $A$ is a $p$-power order abelian group. Let $p^e$ be the exponent of $A$, so $A$ is a ${\mathbb Z}/p^e {\mathbb Z}$-module. Choose an element $a \in A$ of order $p^e$. Then we have ${\mathbb Z}/p^e {\mathbb Z} \hookrightarrow A,$ an embedding of ${\mathbb Z}/p^e {\mathbb Z}$-modules. Sincer ${\mathbb Z}/p^e$ is injective over itself, this splits. (There are many elementary ways to prove this, or to alter the argument: e.g. apply Pontrjagin duality, which for a group of exponent $p^e$ is just Homs to ${\mathbb Z}/p^e {\mathbb Z},$ to get a surjection from a ${\mathbb Z}/p^e {\mathbb Z}$-module to ${\mathbb Z}/p^e {\mathbb Z}$, which must then split, the latter being free of rank one; now apply Pontrjagin duality again to get a splitting of the original sequence.)
Continuing by induction on the order, we write $A$ as a sum of cyclic groups of $p$-power order.
(5) We have now shown that any f.g. $A$ is a direct sum of a free group and of cyclic groups of prime power order. It is easy to rearrange this information to get the classification in terms of elementary divisors.
Comment: while this may not seem so slick, I think it has the merit that the techniques it uses are elementary versions of standard commutative algebra arguments for analyzing modules over any commutative Noetherian ring, namely various localization and devissage techniques.
E.g. the preceding argument extends immediately to the PID case. In step (1), one uses the PID property to find a common denominator, rather than the Euclidean algorithm.
In step (3), one observes that $A_{tors}$, being finitely generated and torsion, is annihilated by some non-zero ideal $I$ in the PID $R$, hence is a module over the Artinian ring $R/I$, and so is the sum of its localizations $A_{\mathfrak p},$ where $\mathfrak p$ ranges over the finitely many (non-zero, hence maximal) prime ideals containing $I$.
EDIT: If one wants to work more in the spirit of the classification by elementary divisors, and avoid working one prime at a time, one can combine steps (3), (4), and (5) as follows:
(3') Suppose $A$ is f.g. torsion. Let $e$ be its exponent. Then it is a ${\mathbb Z}/e{\mathbb Z}$-module, and contains an element of order $e$. Thus one has an embedding ${\mathbb Z}/e{\mathbb Z} \hookrightarrow A,$ which must split (either by the injectivity argument of (3), applied now to ${\mathbb Z}/e{\mathbb Z}$, or the Pontrjagin duality argument). Proceeding by induction, one writes $A = \oplus {\mathbb Z}/e_i{\mathbb Z},$ where $e_i | e_{i-1},$ as required.
EDIT: Suppose that one wants to prove directly that ${\mathbb Z}/e{\mathbb Z}$ is injective as a module over itself (as Martin asks below): using a standard criterion for injectivity of modules over a commutative ring, one need just show that for any ideal $I$ of ${\mathbb Z}/e{\mathbb Z}$, any map $I \hookrightarrow {\mathbb Z}/e{\mathbb Z}$ of extends to a map ${\mathbb Z}/e{\mathbb Z} \rightarrow {\mathbb Z}/e{\mathbb Z}$.
This is easily done: $I$ is of the form $f {\mathbb Z}/e{\mathbb Z}$, for some $f | e$. Equivalently, $I = ({\mathbb Z}/e{\mathbb Z})[e/f]$ (the $e/f$-torsion submodule). The given map $I \rightarrow {\mathbb Z}/e{\mathbb Z}$ then necessarily lands in $({\mathbb Z}/e{\mathbb Z})[e/f] = I,$ and a map $I \rightarrow I$ can certainly be extended to a map ${\mathbb Z}/e{\mathbb Z} \rightarrow {\mathbb Z}/e{\mathbb Z}$, as required.
