In "Mathematical Logic, by Joseph R. Shoenfield" we find an exercise to prove it from ZFC. Would it be possibly to prove the Tukey lemma also from ZC only, i.e. without making use of the axiom schema of replacement.
You are not really using Replacement. You are using transfinite recursion over a long enough well-order.
But Replacement is not necessary for Hartogs' theorem, which then only gives you a well-ordered set, just not a von Neumann ordinal. And Replacement is not necessary for phrasing transfinite recursion over an existing well-order.
So yes, Zermelo + Choice is enough to prove the Teichmüller–Tukey lemma.