Algebraic closure for $\mathbb{Q}$ or $\mathbb{F}_p$ without Choice?
For any finite or countable field $K$, you can well-order $K$ even without AC, and then you don't actually need any further choice to construct a closure for it.
Namely, since $K$ can be well-ordered, you can well-order all monic polynomials over $K$ and adjoin roots for the irreducible ones one by one by transfinite induction up to $\omega_1$. Each time we adjoin elements, we can well-order the new elements and stick them at the end of the well-ordering of the ones we already have. If we order the polynomials primarily by "maximal coefficient" rather than by degree, the new polynomials that become possible after each extension will always come after the ones we already know.
By the time we reach $\omega_1$, there cannot be any more polynomials that need to have roots adjoined. Namely, every polynomial we can form at that point will have had each of its coefficients added at a time when there were only countably many polynomials in our list of polynomials to process, so this polynomial will have been processed at some step before $\omega_1$.
Edit to add: In fact, as Zhen Lin points out, one only has to adjoin roots for polynomials with coefficients in $K$. For $K=\mathbb Q$ that is shown in this question, but the arguments there appear to work in general. This is easy enough to do for any well-orderable $K$, not just countable ones.
Actually, according to this FOM post, Wilfrid Hodges [1975, Läuchli's algebraic closure of $\mathbb{Q}$] proved that ZF is not enough to prove the existence of a unique algebraic closure of $\mathbb{Q}$, where he takes algebraic closure to mean an algebraically closed field containing (an isomorphic copy of) $\mathbb{Q}$ and no other strictly smaller algebraically closed subextension.
On the other hand, in the same post, Stephen Simpson asserts that every countable field $K$ admits a unique (up to non-unique isomorphism) countable algebraic closure, in the sense of a countable algebraically closed field containing (an isomorphic copy of) $K$ whose elements are all algebraic over (the copy of) $K$.
As far as I can tell, the construction given by Henning Mahkolm below should work to construct an algebraic closure of $\mathbb{Q}$, and so should Arturo Magidin's suggestion (modulo proving that $\mathbb{C}$ has all roots of all polynomials over $\mathbb{Q}$). Here is the required fact to pass from one to the other:
Proposition. Let $L$ be a field extension of $K$. If every polynomial over $K$ splits over $L$, then there is a unique subextension $\overline{K}$ such that
- $\overline{K}$ is an algebraically closed field.
- $\overline{K}$ is minimal with respect to this property.
Proof. Let $\overline{K} = \{ x \in L : x \text{ is algebraic over } K \} $. Clearly, if we can show (1), (2) will follow by construction: any algebraically closed subextension of $L$ must contain $\overline{K}$ as a subset.
By the usual dimension arguments – which I believe are allowed since we only need to work with finite-dimensional vector spaces over $K$ – it can be shown that $\overline{K}$ is a subfield of $K$: the key point is that if $K'$ is a finite extension of $K$ and $K''$ is a finite extension of $K'$, then $K''$ is a finite extension of $K$, and if $x$ is algebraic over $K'$ then $K'(x)$ is finite over $K'$, so $x$ is algebraic over $K$ itself.
Now, consider an arbitrary polynomial $p$ over $\overline{K}$. Since $p$ only has finitely many coefficients, it is in fact a polynomial over some subfield $K'$ which is a finite extension of $K$. So it is enough to show that, for any finite subextension $K'$, every polynomial $p$ over $K'$ splits over $\overline{K}$. But $K'$ is finite over $K$, so every root of $p$ must be algebraic over $K$, and every polynomial over $K$ splits over $\overline{K}$ by hypothesis, so $p$ must split over $\overline{K}$ as well, and hence, over $\overline{K}$. So $\overline{K}$ is indeed algebraically closed.
Regardless, a few of the things we want algebraic closures for can be done by hand in the absence of choice. For example:
Lemma. Let $K$ be a field, and let $K \hookrightarrow L$ and $K \hookrightarrow L'$ be any two finite extensions. Then, there is a finite extension $K \hookrightarrow M$ containing isomorphic copies of $L$ and $L'$ as subextensions.
Proof. Let $A = L \otimes_K L'$. This is a finite-dimensional $K$-algebra. As such, it has a finite upper bound on lengths of strictly ascending chains of ideals, and therefore contains a maximal ideal $\mathfrak{m}$. (Note: this is much stronger than the usual ascending chain condition, and the ascending chain condition is not enough to prove the existence of maximal ideal! See [Hodges, 1973, Six impossible rings].) It is easy to check that the field $M = A / \mathfrak{m}$ has the desired properties.
Lemma. Let $K$ be a field, and let $p$ be a polynomial over $K$. Then, there is an extension $K \hookrightarrow L$ which splits $p$.
Proof. By the preceding lemma, if we can do this for irreducible polynomials, then we can do this for all polynomials. We may assume $p$ is irreducible of degree at least 2. Observe that $K' = K[x] / (p)$ is a field, and $p$ factors over $K'$ into polynomials of strictly lower degree. The result follows by induction on the degree of $p$.
So as long as we are content to only work with finitely many polynomials at any time, things should be fine...