The ordinal $\omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $\mathsf{ZF}$ that ${\mathbb R}$ is a countable union of countable sets. From this, it follows easily that $\omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $\omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $\mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $\omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $\omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $\omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $\mathsf{ZF}$ that there are no cardinals $\kappa$ such that $\aleph_0<\kappa<\aleph_1$". This is true, but it is stronger than that: By definition $\aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $\aleph_0$ and $\aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $\kappa$ and its successor $\kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $\aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $\omega_2$, we check more generally that if $\kappa$ is a (well-ordered) cardinal, then a union of $\kappa$ many sets, each of size at most $\kappa$, cannot have size $\kappa^{++}$: Let $S_0,S_1,\dots,S_\beta,\dots$, $\beta<\kappa$, be sets of ordinals, each of size at most $\kappa$. Let $S$ be their union and let $\alpha={\rm ot}(S)$, the order type of $S$. Similarly, let $o_\iota={\rm ot}(S_\iota)$ for each $\iota<\kappa$. Each $o_\iota$ is an ordinal below $\kappa^+$ and therefore $o=\sup_\iota o_\iota\le\kappa^+$. Use this to define a surjection $f$ from $\kappa\times o$ onto $\alpha$, from which it follows that there is an injection from $\alpha$ into $\kappa\times o$, and therefore a injection from $\alpha$ into $\kappa^+$:
Given $(\iota,\beta)\in \kappa\times o$, define $f(\iota,\beta)=0$ unless $\beta<o_\iota$ and, letting $\gamma$ be the $\beta$-th element in the increasing enumeration of $S_\iota$, we have that $\iota$ is least such that $\gamma\in S_\iota$. If this is the case, then set $f(\iota,\beta)=\delta$, where $\delta$ is defined so that $\gamma$ is the $\delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $\omega_1$ can be written as the countable union of countable sets, then any $\alpha<\omega_2$ can be written this way as well, so $\omega_2$ cannot be replaced with any smaller bound.)
Note that $\omega^\omega$ is not the ordinal exponentiation, but rather the set of all functions from $\omega$ to itself. It is easy, and I leave it to you, to verify that this is in fact a set of cardinality $2^{\aleph_0}$ (if you give up, it has been asked on this site infinitely many times before), so definitely not $\aleph_0$, but not necessarily $\aleph_1$ either if you don't assume more than just $\sf ZFC$.
So you shouldn't assume that this is a countable set (you can, but equally you can just assume that $0=1$ or something). The set that you suggest, which is the eventually zero sequences, is a countable set which is also dense. This set witnesses the fact that the Baire space is a separable space.
For the Borel hierarchy basic books about descriptive set theory such as Kechris' and Moschovarkis' books can be good. Jech's Set Theory also has a chapter with the basic information in the first part.
Also, the first ordinal of size $\aleph_1$ is no other than $\omega_1$. We cannot represent it in a better way using ordinal arithmetic because ordinal arithmetic preserves cardinality, so $\alpha^\beta+\gamma\cdot\delta+\eta$ is countable if all $\alpha,\beta,\gamma,\delta,\eta$ are countable. Since $\omega_1$ is not countable, it cannot be written that way.
Related:
Best Answer
There are two things here which you somewhat merge together.
First, the naive answer, $c$ is either $0$ or $1$, or any infinite cardinal. To see that, note that $c^2=c$ holds exactly in those cases. Now for each $S\in\scr S$ choose a bijection with $c$, and we just get $c^2$.
Now, what about the "finite unions of finite sets are finite"? That's not really a cardinality. Instead, this is "the union of fewer than $\aleph_0$ sets, each of size less than $\aleph_0$ is also smaller than $\aleph_0$". So the question is "If $|\mathscr S|< c$ and each $S\in\scr S$, $|S|<c$, then $|\bigcup\mathscr S|<c$".
This is exactly the same as claiming that $c$ is a regular cardinal, which includes all the successor cardinals, $\aleph_0$, and the (weakly) inaccessible cardinals.