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.)
The axiom of well-ordered choice, or $\sf AC_{\rm WO}$, is strictly weaker than the axiom of choice itself. If we start with $L$ and add $\omega_1$ Cohen reals, then go to $L(\Bbb R)$, one can show that $\sf AC_{\rm WO}$ holds, while $\Bbb R$ cannot be well-ordered there.
Pincus proved in the 1970s that this is equivalent to the following statement on Hartogs and Lindenbaum numbers:
$\sf AC_{\rm WO}$ is equivalent to the statement $\forall x.\aleph(x)=\aleph^*(x)$.
Here, the Lindenbaum number, $\aleph^*(x)$, is the least ordinal which $x$ cannot be mapped onto. One obvious fact is that $\aleph(x)\leq\aleph^*(x)$.
In the late 1950s or early 1960s Jensen proved that this assumption also implies $\sf DC$. This is also a very clever proof.
The conjunction of these two consequences gives us that $\aleph_1\leq 2^{\aleph_0}$, as a result of a theorem of Shelah from the 1980s, this implies there is a non-measurable set of reals.
As far as Hahn–Banach, or other things of that sort, I do not believe that much is known on the topic. But to sum up, this axiom does not imply that the reals are well-ordered, but it does imply there is a non-measurable set of reals because there is a set of reals of size $\aleph_1$ and $\sf DC$ holds. Moreover, it is equivalent to saying that the Hartogs and Lindenbaum numbers are equal for all sets.
Best Answer
Yes, you're right, it should have said that choice is necessary for proving that $\omega_1$ is regular. And indeed it is consistent with $\sf ZF$ that $\omega_1$ is singular.
However, you're wrong about a well ordered union of well ordered sets. For example, the real numbers could also be a countable union of countable sets (this is true in the first model in which $\omega_1$ is singular, due to Feferman and Levy). Or, the classic example of a set of socks which is a countable union of pairs which is Dedekind finite (so there is no infinite set of these pairs that admits a choice function).
Of course, if we understand "well ordered set" as a set with a specified well order, then it is indeed the case that a well ordered union of well ordered sets is well ordered. The key problem in the above examples is exactly that we cannot choose a well ordering in a uniform manner.