Is there any easy existential proof of transcendental numbers without choice?

Background: I was reading the following comment from the meta site:

"One can easily show that transcendental numbers exist, but to show that a single particular number is transcendental is a very different question."

The usual "easy" proof that transcendental numbers exist goes like this:

However, let $P_n$ be the set of all degree-$n$ polynomials with integer coefficients. Then $P_n$ can be enumerated in a way similar to the enumeration of rationals. The set of all algebraic numbers, $\bigcup_{n\in\mathbb N}\bigcup_{p\in P_n}\bigcup\{\omega:p(\omega)=0\}$, is therefore a countable union of countable union of finite sets. I have read that "it is consistent with ZF that $\mathbb R$ is a countable union of countable sets". So, without the help of some sort of choice, a countable union of countable sets is not always countable. I know only very little set theory, but this makes me question the validity of step 1 above.

Here are my questions: without assuming any kind of axiom of choice, is the proof above valid? If not, is Liouville's constructive proof (using $\sum_{k=0}^\infty 10^{-k!}$) already the easiest existential proof?

There is no need for choice. Although ZF can't prove that a countable union of finite sets is countable, it can prove that a countable union of finite sets of real numbers is countable. This is just because the real numbers have a linear ordering (provably in ZF), so any finite set of real numbers is already ordered for you and you don't need to choose the ordering of each set when you do the proof.

(And there is no issue with showing that the number of polynomials with integer coefficients is countable either, as here we are just doing a count of finite sets of integers, which are well ordered already.)