I was reading "Introduction to Set Theory" - Thomas Jech, and up until the Recursion Theorem section only the following axioms were presented: Extensionality, Comprehension, Pair, Union, Power and Infinity, so I have something like $Z^- - C$, but In this chapter he says:
$Seq(A) = \bigcup_{n\in\mathbb{N}}A^n$ denotes the set of all finite sequences of elements of $A$. (Prove that it exists!)
How exactly do I justify the existence of $X=\{A^0,A^1,\dots\}$ in order to define $\bigcup X$, the only way I see to do this is using the Axiom of Substitution , but it's only introduced 3 chapters later, so my question is:
Is it possible to prove in $Z^- - C$ that $Seq(A)$ always exists?
And if not, how can I create a model $M\vDash Z^- - C$ that does not have $Seq(A)$, for some $A$.
You are on the right track indeed, you can simply note that $f\in\operatorname{Seq}(A)$ if and only if $f\subseteq n\times A$ is a function for some $n<\omega$. Therefore, the whole set is merely a subset of the power set of $\omega\times A$.
Your original approach of defining $A^n$ and obtaining $\bigcup A^n$, while fine once the above has been established, is one of the reasons why Replacement is a useful axiom in mathematics (contrary to what some people say). It allows us to simplify arguments, and it allows us to think about $A^n$ as a recursive definition: $A^{n+1}=A^n\times A$. Indeed, if we want to use this recursive definition, Replacement is necessary, since $V_{\omega+\omega}$ would be a model of $\sf ZC$, where $\operatorname{Seq}(\Bbb R)$ would not exist in this way.
(And yes, you can redefine the ordered pairs to not increase in rank and therefore be compatible, at least a bit better, with $\sf Z$ (or at least $\sf Z$ augmented with some kind of a von Neumann hierarchy), but the whole idea behind Replacement is that the choice of coding does not matter.)