Q:

The regularity of successor cardinal

I was looking at two different proofs of the fact that successor cardinals are regular. It struck me as odd that both proofs used AC. Looking at the concepts involved in defining cofinality I feel as if there should a proof of this that doesn't use AC.
So, is my intuition correct or is this statement dependent on AC? Also in either case could you point me to a reference to the fact?

A:

The statement depends on the axiom of choice. It is consistent, modulo large cardinals, that all (well-ordered) infinite cardinals have cofinality $\omega$. 
This was first proved by Gitik, around 1980, from a proper class of strongly compact cardinals. The result is significant, and rather involved. It is actually an interesting construction. In a forcing extension of the universe, a suitable inner model $N$ (of $\mathsf{ZF}$) is identified and a cardinal $\kappa$ such that, inside that model, the level $N_\kappa$ is shown to satisfy the statement. I do not think we have models of the statement obtained by class forcing, without at the end cutting the universe at some level.
The result has been improved since, reducing the large cardinals involved, but they are still pretty large, beyond anything we can reach with inner model theory. The best lower bound that we know of is that the statement that all cardinals are singular implies that $\mathsf{AD}$ holds in the $L(\mathbb R)$ of some suitable inner model of a forcing extension. This is a fairly recent (2008) result due to Ralf Schindler and Daniel Busche, see here. Again, it would be interesting to get the result directly in $V$ without having to pass to an extension, but technical difficulties in the implementation of the technique known as the core model induction prevent us from doing this at the moment. 
(That large cardinals were needed at all has been known for a long while. A nice short argument, due to Magidor, shows how the fact that $\omega_1$ and $\omega_2$ are singular violates the covering lemma in some inner model and therefore implies that $0^\sharp$ exists, see here.)

A:

Let me add on Andres' wonderful answer, something which I think is missing.
Despite the necessity of large cardinals, it was in fact one of the first uses of the technique of forcing (and symmetric extensions) to show that in fact $\omega_1$ and $\Bbb R$ can be countable unions of countable sets.
This is a classical result due to Feferman and Levy. In her Ph.D. Thesis Ioanna Dimitriou extended this result, and proved the following theorem:

Theorem (2.10) If $V$ is a model of $\sf ZFC$, $\kappa_0$ is a regular cardinal of $V$ and $\rho$ is an ordinal in $V$, then there is a model of $\sf ZF$ with a sequence of successive alternating singular and regular cardinals that starts at $\kappa_0$ and that contains $\rho$-many singular cardinals.

And all that without large cardinals. The large cardinals come into play when we want two successive singular cardinals.

