The point is that without the Axiom of Choice, cardinalities are not linearly ordered, and it is possible under $\neg AC$ that there are additional cardinalities to the side of the $\aleph$'s. Thus, the issues is not additional cardinalities between $\aleph_0$ and $\aleph_1$, but rather additional cardinalities to the side, incomparable with these cardinalities.
Let me explain. We say that two sets $A$ and $B$ are equinumerous or have the same cardinality if there is a bijection $f:A\to B$. We say that $A$ has smaller-or-equal cardinality than $B$ if there is an injection $f:A\to B$. It is provable (without AC) that $A$ and $B$ have the same cardinality if and only if each is smaller-or-equal to the other (this is the Cantor-Shroeder-Bernstein theorem).
Under AC, every set is bijective with an ordinal, and so we may use these ordinals to select canonical representatives from the equinumerosity classes. Thus, under AC, the $\aleph_\alpha$'s form all of the possible infinite cardinalities.
But when AC fails, the cardinalities are not linearly ordered (the linearity of cardinalities is equivalent to AC). Let me mention a few examples:
It is a consequence of the Axiom of Determinacy that there is no $\omega_1$ sequence of distinct reals. Thus, in any model of AD, the cardinality of the reals is uncountable, but incomparable to $\aleph_1$. Thus, in such a model, it is no longer correct to say that $\aleph_1$ is the smallest uncountable cardinal. One should say instead that $\aleph_1$ is the smallest uncountable well-orderable cardinal.
A more extreme example is provided by the Dedekind finite infinite sets. These sets are not finite, but also not bijective with any proper subset. It follows that they can have no countably infinite subsets. In particular, they are uncountable sets, but their cardinality is incomparable with $\omega$. Thus, in a model of $\neg AC$ having a Dedekind finite infinite set, it is no longer correct to say that $\aleph_0$ is the smallest infinite cardinal.
Thus, the issue isn't whether there is something between $\aleph_0$ and $\aleph_1$, but rather, whether there are additional cardinalities to the side of these cardinalities.