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
Here's an approach that, in a sense, combines both methods you were considering. The idea is to inductively embed ordinals into $(X, \le_X)$ until you can't any more, and then deduce that the ordinal you finished up with is the ordinal you seek.
First note that $(0, \in)$ embeds trivially into $(X, \le_X)$.
Suppose there is an embedding $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$, and consider the set $X_{\alpha} = X \setminus i_{\alpha}[\alpha]$.
Now suppose $\beta$ is a limit ordinal and that there are embeddings $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$ for each $\alpha < \beta$ such that $i_{\alpha} \subseteq i_{\alpha'}$ for all $\alpha \le \alpha' < \beta$. Define $i_{\beta} = \bigcup_{\alpha < \beta} i_{\alpha}$ and note that $i_{\beta}$ is an embedding $(\beta, \in) \hookrightarrow (X, \le_X)$.
This process must eventually terminate, since $(\alpha, \in)$ does not embed into $(X, \le_X)$ whenever $|\alpha| > |X|$, and the only way it can terminate is when for some $\alpha$ we have $i_{\alpha} : (\alpha, \in) \hookrightarrow (X, \le_X)$ and $X_{\alpha} = \varnothing$.
There are a couple of gaps in the proof to be filled in, but I'm sure you can flesh out the details.