We can do much better than $\epsilon_0$ in Z - we can construct uncountable well-ordered sets! The key observation is that, while building long ordinals uses Replacement, building long well-ordered sets is really a job for just Powerset and Separation.
It's a good exercise to verify the following argument:
Z proves that the set $\mathcal{R}$ of all binary relations on $\omega$ exists.
Z then proves that the subset $\mathcal{W}\subseteq\mathcal{R}$ of all well-founded binary relations on $\omega$ exists.
Z then proves that the set $\mathcal{W}'$ of equivalence classes of elements of $\mathcal{W}'$ under the relation "are order-isomorphic" exists.
Finally, Z proves that the relation $\mathcal{L}\subseteq\mathcal{W}'\times\mathcal{W}'$ given by "is longer than" exists.
But now the pair $\mathfrak{O}=(\mathcal{W}', \mathcal{L})$ is an uncountable well-ordered set, provably in Z (by the usual argument). So we have:
Even though the ordinal $\omega_1$ doesn't provably exist in Z, we can emulate its construction by working with sets of natural numbers.
We can go much further: the above argument shows that for any set $A$, we can form the well-order $Ord(A)$ of ordertypes of well-ordered relations on subsets of $A$. In particular, we can apply this to $\mathfrak{O}$ to build a version of $\omega_2$, and so on. In fact, we can prove in Z that for every $n$, a version of $\omega_n$ exists (of course we have to phrase this rather carefully); conversely, it's consistent with Z that every well-ordered set is order-isomorphic to a subset of one of these versions, so in a sense Z "reaches up to" the ordinal $\omega_\omega$.
(Towards interpreting the previous sentence, it's a good exercise to show that in $(V_{\omega+\omega})^L$, the smallest transitive model of Z, the lengths of the well-ordered sets are exactly the ordinals $<\omega_\omega^L$. If you're not familiar with the "[stuff]$^L$" notation, then work with $V_{\omega+\omega}$ instead and assume GCH.)
