We start by a simple observation which is true for any totally ordered set, not only for well-ordered sets.
Let $(X,\le)$ be a linearly ordered set. We will use the notation $X_a=\{x\in X; x<a\}$ pre $a\in X$. Notice that these sets are initial segments of $X$.
Observation. Let $(X,\le)$ be a linearly ordered set and let $X'=\{X_a; a\in X\}$. Then the function $f\colon X\to{X'}$ defined as
$$f(a)=X_a$$
is an isomorphism between the ordered sets $(X,\le)$ and $(X',\subseteq)$.
Proof. We can see immediately that $f$ is surjective. If $a<b$ then $a\in X_b$ and $a\notin X_a$, so $f(a)=X_a\ne X_b=f(b)$. The case $b<a$ is symmetric. So it is also injective.
The map $f$ is monotone: If $a \le b$ then $f(a)=\{x\in X; x<a\} \subseteq \{x\in X; x<b\}=f(b)$. (It suffices to notice that
$x<a$ and $a\le b$ implies $x<b$ by transitivity.)
To see that also $f^{-1}$ is monotone, we notice that $X_a\subseteq X_b$ implies $a\le b$. (If we had $a>b$, then $b\in X_a\setminus X_b$, which contradicts $X_a\subseteq X_b$.) $\hspace{1cm}\square$
Side remark. Notice that we have used linearity of $\le$ in the above proof. The version of the above observation with $\{x\in X; x\le a\}$ instead of $X_a$ is true also for partially ordered sets and it implies that every partially ordered set is isomorphic to some system of sets ordered by inclusion (in fact, to a subset of $(\mathcal P(X),\subseteq)$.) See, for example, Theorem 1.11 in S. Roman: Lattices and Ordered Sets or this question.
How does this relate to ordinals? We can view ordinals as representatives or order types of well-ordered sets. (At least if we approach them in the naive rather than axiomatic way.) We can define inequality between ordinals via initial embeddings of the corresponding well-ordered sets. (I.e., ordinal type of $(A,\le)$ is less or equal to ordinal type of $(B,\preceq)$ iff $A$ is isomorphic to an initial segment of $B$. This seems to be the natural way how to compare ordinals/well-ordered sets.)
So the above lemma shows that a well-ordered set $X$ is isomorphic to the set of proper initial segments of $X$. Ordinal types of these initial segments are precisely the ordinals lesser than the ordinal type of $X$.
Yes, we can prove the existence of an uncountable well-ordered set without Replacement.
In Z alone (= ZF without Replacement), we can prove the existence of the set $X$ of equivalence classes of well-orderings of $\omega$ modulo order-isomorphism. It's easy to prove that $X$ is uncountable; the only remaining task is to show that $X$ is well-ordered by "$[x]\triangleleft[y]$ iff $x$ order-embeds as an initial segment of $y$" (this relation is clearly well-defined).
It's worth taking a bit of care here, however: the linearly-ordered-ness of $X$ depends on the ability to compare well-orderings, and this is a accomplished via transfinite recursion, but often arguments via transfinite recursion rely on Replacement. This is a reasonable source of worry, but it turns out to not be an issue here: since the "target" of our recursion is a set already, we don't actually need Replacement (see Eric's comment below).
Let me sketch how we can prove that $X$ is linearly ordered by $\triangleleft$ without relying on Replacement:
Say that $\alpha:A\rightarrow B$ is an initial segment embedding (where $A, B$ are linear orders) if it is order-preserving and has range an initial segment of $B$ (possibly all of $B$). We can show without Replacement that if $A, B$ are well-orderings, then there is at most one initial segment embedding from $A$ to $B$. (Think about the least element of the domain on which the two embeddings disagree ...)
Now suppose $A, B$ are well-orderings of $\omega$ and there is no initial segment embedding of $B$ into $A$ (that is, $B\not\trianglelefteq A$); we want to show that there is an initial segment embedding of $A$ into $B$ with range a proper subset of $B$ (so $A\triangleleft B$).
Let $S$ be the set of $a\in A$ such that there is an initial segment embedding from $(a)_A:=\{a'\in A: a'\le_Aa\}$ to $B$. Each $a\in S$ corresponds to a unique element $\hat{a}$ in $B$ by the observation two bulletpoints above; it's easy to see that the (a priori partial) map $m:\alpha\mapsto\hat{\alpha}$ exists and is an initial segment embedding.
Note that $m$ can't be surjective; otherwise, inverting $m$ would give an initial segment embedding of $B$ into $A$.
Now suppose $dom(m)$ is not all of $A$. Let $s$ be the $A$-least element of $A\setminus S$ and (by the above bulletpoint) let $t$ be the $B$-least element of $B\setminus ran(m)$. Then we can extend $m$ to a strictly larger partial initial segment embedding by sending $s$ to $t$, which is a contradiction.
So $dom(m)=A$; that is, $A\triangleleft B$.
It now only remains to show that $X$ has no $\triangleleft$-descending sequences, but this proceeds exactly as usual.
So the existence of big ordinals is much murkier than the existence of big well-orderings (indeed, ZC doesn't even prove that $\omega+\omega$ exists!). You should think of ordinals as being "normal forms" of well-orderings: in general, we need Replacement to show that an arbitrary well-ordering has a normal form.
Best Answer
The key problem in the absence of the axiom of replacement is that there may be well-ordered sets $S$ that are too large in the sense that they are longer than any ordinal. In that case, the collection of ordinals isomorphic to an initial segment of $S$ would be the class of all ordinals, which is not a set.
For example, with $\omega$ denoting as usual the first infinite ordinal, consider the set $V_{\omega+\omega}$. Recall that $V_0=\emptyset$, $V_{\alpha+1}=\mathcal P(V_\alpha)$ and $V_\lambda=\bigcup_{\beta<\lambda}V_\beta$ for all ordinals $\alpha$ and all limit ordinals $\lambda$. The set $V_{\omega+\omega}$ is a model of all axioms of set theory, except for the axiom of replacement. And indeed the theorem that every well-ordered set is isomorphic to an ordinal fails badly here: The ordinals in this model are precisely the ordinals smaller than $\omega+\omega$. However, all well-orderings of $\omega$ belong to $V_{\omega+\omega}$, and many are much longer than this bound (and much more is true, as $V_{\omega+\omega}$ contains plenty of uncountable well-orderings as well).
In this model, if you take as $S$ a well-ordering of $\omega$ of type $\omega+\omega$, then $T=S$, as each proper initial segment of $S$ has order type isomorphic to an ordinal smaller than $\omega+\omega$. However, the collection of ordinals isomorphic to an initial segment of $S$ is all of $\omega+\omega$, which is not a set from the point of view of the model. (And note that there is nothing difficult about finding an $S$ as indicated: Consider for instance the ordering of $\mathbb N$ where the odds and the evens are ordered as usual, but we make every odd number larger than every even number. To get a larger order-type, simply add an extra point on top of all of these.)
Of course, by taking as $S$ something longer, the problem is highlighted even more: Now $T$ is not all of $S$, and the collection of ordinals isomorphic to an initial segment of $S$ is again the class of all ordinals ($\omega+\omega$, in this case).
Maybe this illustrates how replacement avoids this problem: Suppose replacement holds (together with the other axioms) and we know that all ordinals smaller than $\omega+\omega$ "exist" (i.e., are sets). If $S$ is a well-ordered set of type $\omega+\omega$, then $\omega+\omega$ is the collection of ordinals isomorphic to a proper initial segment of $S$. Since $S$ is a set, then $T$ (which is a subclass of $S$) is also a set (in the case being discussed, $T=S$, of course). We know that each member $x$ of $T$ corresponds to a unique ordinal (i.e., there is a unique ordinal isomorphic to the initial segment of $S$ determined by $x$). By replacement, this means that the collection of all these ordinals is a set (it is the image of the set $T$ under the function mapping $x$ to the ordinal $S_x$ is isomorphic to). That is, $\omega+\omega$ exists as well.
If you examine the proof of the theorem you will see that the argument is essentially inductive: You go bit by bit ensuring that all initial segments of $S$, including $S$ itself, correspond to some ordinal. The proof, however, is usually not organized as an induction. Rather, you start with $S$ that is well-ordered. You extract $T$ from $S$ and note it is a (not necessarily proper) initial segment of $S$. You use replacement to conclude that there is a set of ordinals associated to $T$ as indicated. You argue that since $T$ is an initial segment of $S$, then this set of ordinals is also an ordinal, call it $\alpha_T$, which leads you to the conclusion that $T$ is order isomorphic to $\alpha_T$. Now you conclude that $T$ is indeed $S$, and you are done. The point is that if $T$ is not $S$, then $T=S_y$ for a unique $y\in S$, and we just proved that $S_y$ is order isomorphic to an ordinal, namely $\alpha_T$, so $y$ would have been in $T$ as well, and we get a contradiction.