In the absence of the axiom of choice, it is still possible to define the "usual" algebraic closure of $\mathbb{Q}$ because you can just explicitly enumerate all polynomials with integer coefficients. Richard Taylor's remark should be interpreted as referring to this particular algebraic closure.
What you can't prove without choice is the uniqueness of the algebraic closure. Exotic algebraic closures could exist. So in the absence of choice, it's a bit misleading to use the notation $\overline{\mathbb{Q}}$ as if it referred to some unique thing. Wilfrid Hodges, in his paper, Läuchli's algebraic closure of $Q$, shows that an exotic algebraic closure of $\mathbb{Q}$ can have all kinds of unexpected properties. But what this shows, in my opinion, is that what we usually think of as "algebraic number theory" doesn't make too much sense in that context. When people talk about "algebraic number theory" they are tacitly referring to the usual algebraic closure.