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.)
Mike: If you fix an ordinal $\alpha$, then it is consistent that ${\mathfrak c}>\aleph_\alpha$. More precisely, there is a (forcing) extension of the universe of sets with the same cardinals where the inequality holds.
If you begin with a model of GCH, then you can go to an extension where ${\mathfrak c}=\aleph_\alpha$ and no cardinals are changed, as long as $\alpha$ is not a limit ordinal of countable cofinality. For example, $\aleph_{\aleph_\omega}$ is not a valid size for the continuum. But it can be larger.
Here, the cofinality of the limit ordinal $\alpha$ is the smallest $\beta$ such that there is an unbounded function $f:\beta\to\alpha$. There is a result of König that says that $\kappa^\lambda>\kappa$ if $\lambda$ is the cofinality of $\kappa$. If $\kappa={\mathfrak c}$, this says that $\lambda>\omega=\aleph_0$, since ${\mathfrak c}=2^{\aleph_0}$ and $(2^{\aleph_0})^{\aleph_0}=2^{\aleph_0}$. Since $\aleph_{\aleph_\omega}$ has cofinality $\omega$, it cannot be ${\mathfrak c}$.
But this is the only restriction! The technique to prove this (forcing) was invented by Paul Cohen and literally transformed the field.
Best Answer
You've made a very big mess, I think. The way you defined cardinal numbers is very awkward, so to say. In my eyes, anyway.
Let us review the construction of ordinals:
Now we define initial ordinals as ordinal numbers which cannot be bijected with any smaller ordinal. For example $\omega$ (the set of natural numbers) is such ordinal, while $\omega+1, \omega+\omega, \omega\cdot\omega$ are not initial ordinals.
Under the axiom of choice, every set is well-orderable, and therefore we can choose the initial ordinal out of each equivalence class as a representative. This is the usual notion of $\aleph$ numbers under the axiom of choice.
Without assuming choice, the cardinal system is not well-ordered and can behave very strangely.
Regardless to that, when you are only dealing with ordinals you don't need choice because there is a canonical choice function (take the minimal element). So even without the axiom of choice it is true that $\omega_\alpha$ has no bijection with $\omega_\beta$ for $\alpha\not=\beta$.
The idea behind aleph numbers, as far as I see it, is that it is a well ordering of cardinalities (not necessarily all cardinalities, though) and as such it holds just fine even when not assuming choice. However, in the case you don't have the axiom of choice to help you out, $2^{\aleph_0}$ might not be well-orderable and thus won't be represented by an ordinal, and therefore won't be represented by an $\aleph$ number, same with multiplication. It is equivalent to the axiom of choice that for every infinite set $|X| = |X\times X|$.
Just last remark, you said that the construction you gave infers the existence of $\aleph_n$ for every natural number $n$ while in fact it gives you $\aleph_\alpha$ for every ordinal $\alpha$ and not just for the natural numbers.