This is not exactly the question, but it is related.  To begin with, it is difficult to "explicitly" describe $\overline{\mathbb{Q}}$ except as a subfield of $\mathbb{C}$.  I found a paper, [Algebraic consequences of the axiom of determinacy][1] (in English translation of the title) that establishes that $\mathbb{C}$ does not have any automorphisms other than complex conjugation in ZF plus the axiom of determinacy (AD).  So you need some part of the axiom of choice (AC) for this related question.

As for the smaller field $\overline{\mathbb{Q}}$, the Wikipedia page for the fundamental theorem of algebra suggests that you might not even be able to construct it in the first place without the axiom of countable choice.  (I say "suggests" because I'm not entirely sure that that is a theorem.  Note that AC and AD both imply countable choice even though they are enemy axioms.)    Any construction with countable choice isn't truly "explicit".  On the other hand, if you allow countable choice, then I suspect that you can build $\overline{\mathbb{Q}}$ synthetically by induction rather than as a subfield of $\mathbb{C}$, and that you can build many automorphisms of it as you go along.

So the questions for logicians is whether there is a universe over ZF in which $\overline{\mathbb{Q}}$ does not exist, or a universe in which it does exist but has no automorphisms.

  [1]: http://www.ams.org/mathscinet-getitem?mr=756898