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\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.

2more comments