The existence and uniqueness of algebraic closures is generally proven using Zorn's lemma. A quick Google search leads to a 1992 paper of Banaschewski, which I don't have access to, asserting that the proof only requires the ultrafilter lemma. Questions:
Qiaochu, using the link I provided in my answer to this question, you find that this question is still open (or was, as of the mid 2000s, and I haven't heard of any recent results in this direction).
(According to the site's notation, the existence of algebraic closures is form 69, the ultrafilter theorem is form 14, uniqueness of the algebraic closure (in case they exist) is form 233; these numbers can be found by entering appropriate phrases in the last entry form in the page linked to above.)
It is known that uniqueness implies neither existence nor the ultrafilter theorem.
It is open whether existence implies uniqueness or the ultrafilter theorem, and also whether (existence and uniqueness) implies the ultrafilter theorem.
(Enter 14, 69, 233 in Table 1 in the link above for these implications/non-implications.)
Jech's book on the axiom of choice should provide the proofs of the known implications and references, and the book by Howard-Rubin (besides updates past the publication date of Jech's book) provides references for the known non-implications.
Here are some details on Banaschewski's paper:
1. First, lets see that the ultrafilter theorem can be used to prove uniqueness of algebraic closures, in case they exist.
Let $K$ be a field, and let $E$ and $F$ be algebraic closures. We need to show that there is an isomorphism from $E$ onto $F$ fixing $K$ (pointwise).
Following Banaschewski, denote by $E_u$ (resp., $F_u$) the splitting field of $u\in K[x]$ inside $E$ (resp., $F$); we are not requiring that $u$ be irreducible. We then have that if $u|v$ then $E_u\subseteq E_v$ and $F_u\subseteq F_v$. Also, since $E$ is an algebraic closure of $K$, we have $E=\bigcup_u E_u$, and similarly for $F$.
Denote by $H_u$ the set of all isomorphisms from $E_u$ onto $F_u$ that fix $K$; it is standard that $H_u$ is finite and non-empty (no choice is needed here). If $u|v$, let $\varphi_{uv}:H_v\to H_u$ denote the restriction map; these maps are onto.
Now set $H=\prod_{u\in K[x]} H_u$ and for $v|w$, let $$ H_{vw}=\{(h_u)\in H\mid h_v=h_w\upharpoonright E_v\}. $$ Then the Ultrafilter theorem ensures that $H$ and the sets $H_{vw}$ are non-empty. This is because, in fact, Tychonoff for compact Hausdorff spaces follows from the Ultrafilter theorem, see for example the exercises in Chapter 2 of Jech's "The axiom of choice." Also, the sets $H_{vw}$ have the finite intersection property. They are closed in the product topology of $H$, where each $H_u$ is discrete.
It then follows that the intersection of the $H_{vw}$ is non-empty. But each $(h_u)$ in this intersection determines a unique embedding $h:\bigcup_uE_u\to\bigcup_u F_u$, i.e., $h:E\to F$, which is onto and fixes $K$.
2. Existence follows from modifying Artin's classical proof.
For each monic $u\in K[x]$ of degree $n\ge 2$, consider $n$ "indeterminates" $z_{u,1},\dots,z_{u,n}$ (distinct from each other, and for different values of $u$), let $Z$ be the set of all these indeterminates, and consider the polynomial ring $K[Z]$.
Let $J$ be the ideal generated by all polynomials of the form $$ a_{n-k}-(-1)^k\sum_{i_1\lt\dots\lt i_k}z_{u,i_1}\dots z_{u,i_k} $$ for all $u=a_0+a_1x+\dots+a_{n-1}x^{n-1}+x^n$ and all $k$ with $1\le k\le n$.
The point is that any polynomial has a splitting field over $K$, and so for any finitely many polynomials there is a (finite) extension of $K$ where all admit zeroes. From this it follows by classical (and choice-free) arguments that $J$ is a proper ideal.
We can then invoke the ultrafilter theorem, and let $P$ be any prime ideal extending $J$. Then $K[Z]/P$ is an integral domain. Its field of quotients $\hat K$ is an extension of $K$, and we can verify that in fact, it is an algebraic closure. This requires to note that, obviously, $\hat K/K$ is algebraic, and that, by definition of $J$, every non-constant polynomial in $K[x]$ split into linear factors in $\hat K$. But this suffices to ensure that $\hat K$ is algebraically closed by classical arguments (see for example Theorem 8.1 in Garling's "A course in Galois theory").
3. The paper closes with an observation that is worth making: It follows from the ultrafilter theorem, and it is strictly weaker than it, that countable unions of finite sets are countable. This suffices to prove uniqueness of algebraic closures of countable fields, in particular, to prove the uniqueness of $\bar{\mathbb Q}$.
As I mentioned in a comment to Eivind Dahl's answer, it seems that there is also an easy argument directly from the Compactness theorem of first order logic. Since you said you are looking for alternative constructions, let me expand on the idea here.
The Compactness theorem asserts that if every finite subset of a first order theory has a model, then the whole theory has a model. Andres mentioned that this is equivalent to the Ultrafilter lemma.
Existence. Let $F$ be a field. Let $T$ be the theory consisting of the field axioms, the atomic diagram of $F$ (which asserts all the equations and negated equations true in $F$, using constants for elements of $F$), plus the assertions that every polynomial over $F$ has a root. This last assertion is made separately as an assertion about each particular polynomial over $F$, using the constants in the language added for the elements of $F$. This theory is easily seen to be finitely satisfiable, since any finite subtheory mentions only finitely many polynomials of $F$, and we can satisfy it in a finite extension of $F$. Thus, by the Compactness theorem, the whole theory has a model $K$. If we take the collection of elements of $K$ that are algebraic over $F$, this will be algebraically closed.
Uniqueness. Let $F$ be a field and let $E$ and $K$ be algebraic closures of it. Let $T$ be the theory consisting of the union of the atomic diagrams of $E$ and $K$, plus the field axioms. (Note that we haven't added any axioms saying that elements of $E$ and $K$ are distinct, and in the end these constants will be in effect melded together, providing the isomorphism.) If $T_0$ is a finite subtheory, then only finitely many elements of $E$ and $K$ appear. Those elements of $E$ and $K$ appear in some $F[\vec a]\subset E$ and $F[\vec b]\subset K$. We can embed both of these extensions of $F$ into a single finite extension $F[\vec u]$, which will satisfy all assertions in $T_0$. (Note, this embedding effectively decides a little piece of the isomorphism, by mapping some of the $\vec b$'s to some of the $\vec a$'s.) Thus, by Compactness, the whole theory is satisfiable. If $G$ is a model of $T$, then since $G$ interprets the atomic diagrams of $E$ and $K$, we get isomorphisms of $E$ and $K$ into subfields of $G$. These maps agree on $F$ and have a common range, which is the set of elements of $G$ that are algebraic over $F$. Thus, the composition is an isomorphism of $E$ and $K$.
Paolo Aluffi's book "Algebra: Chapter 0" mentions that compactness of first order logic is sufficient to prove this (p. 403). I don't know the ultrafilter lemma.
