Suppose $C$ is a nonempty class of ordinals, and pick some $\alpha\in C$. Either $\alpha$ is the least element of $C$, or it isn't. If it is, we're done. Otherwise, think about $$\alpha\cap C.$$ This is a set of ordinals, and nonempty by assumption on $\alpha$, so it has a least element $\beta$. Now do you see how to argue that $\beta$ is in fact the least element of $C$?
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.
Best Answer
This indeed requires more justification. The key point is that $f$ is injective, so $f^{-1}$ is a well-defined function on the image of $f$. If there does not exist any $\alpha$ such that $f[\alpha]=x$, then $f$ is defined on the entire class $Ord$ of ordinals, and so $f^{-1}$ is surjection $A\to Ord$ where $A$ is the image of $f$ (a set by Separation, since it is a subset of $x$). But then by Replacement the image $f^{-1}[A]=Ord$ is a set, which is a contradiction (by the Burali-Forti paradox).
By the way, it is possible to avoid Replacement in justifying many arguments of this sort. For any set $X$, you can prove (without Replacement or Choice) that there exists a well-ordered set $W$ such that there exists no injection $W\to X$, and then use transfinite recursion on $W$ instead of on $Ord$. See this answer of mine for more details. This doesn't work for a statement like the one you mention where the conclusion itself involves ordinals, but it works for many other proofs whose conclusions aren't about ordinals (e.g., things like "every vector space has a basis", where you construct a basis by building it one element at a time by transfinite recursion).