"...is a proper ideal, and so is contained in a maximal ideal of $A$."
The fact that proper ideals are contained in maximal ideals of rings with unity is actually equivalent to the Axiom of Choice, so this isn't really avoiding AC, it's just hiding it.
There are models of ZF in which there are fields with no algebraic closure, so it's known that you need at least some Choice to prove that every field has an algebraic closure.
There is an article by Bernhard Banaschewski, Algebraic closure without choice, Z. Math. Logik Grundlag. Math. 38 (1992), no. 4, 383-385, which says that you can prove that every field has an algebraic closure if you only assume the Boolean Ultrafilter Theorem, which is strictly weaker than AC.
By the way, the argument given is attributed in Lang's Algebra to Artin.
Re: (4). As you are only "95% sure".....In ZF, without analysis, we have
(i). If $X$ is a compact space and $f:X\to [0,\infty)$ is continuous and $y=\inf_{x\in X}f(x)$ then $\exists x\in X\;(f(x)=y).$ Otherwise $\{f^{-1}(y+r,\infty):r>0\}$ is an open cover of $X$ with no finite sub-cover.
(ii).(Edited). $[-r,r]^2$ is compact for positive real $r$. We derive this from (iii) below. [I don't want to re-number all the references in the second half of this A.]
(iii). A closed bounded real interval is compact.
(iv). (Elementary). For $r>0$ the set $R(r)=\{z\in \mathbb C: \max (|Re (z)|, |Im(z)|)\leq r\}$ is homeomorphic to $[-r,r]^2.$ By (ii) and (iii), $R(r)$ is compact.
(v). (Elementary). If $p:\mathbb C\to \mathbb C$ is a non-constant polynomial then $|p(z)|\to \infty$ uniformly as $|z|\to \infty$. And by elementary algebraic means, $|p|$ is a continuous function.
Theorem. A non-constant polynomial $p:\mathbb C\to \mathbb C$ has a zero. PROOF: The case deg $(p)=1$ is trivial, so assume deg$(p)>1.$
By (v) there exists $r>0$ such that $\forall z \in \mathbb C$ \ $R(r)\;( |p(z)|>|p(0)|).$
Let $R(r)$ be as in (iv). Now $R(r)$ is compact so there exists $z_0\in R(r)$ with $|p(z_0)|=\min \{|p(z)|:z\in R(r)\}.$
We have $|p(z_0)|\leq |p(0)|.$ Also $z\not \in R(r)\implies |p(z)|>p(0)|\geq |p(z_0)|.$ Therefore $$|p(z_0)|=\min \{|p(z)|:z\in \mathbb C\}.$$
We now assume $p(z_0)\ne 0$ and obtain a contradiction.
Since deg$(p)>1$ there exists (unique) $k\in \mathbb N$ and $A\ne 0$ and polynomial $q$ such that $$\forall z\;(p(z)=p(z_0)+A(z-z_0)^k(1+(z-z_0)q(z-z_0)).$$ There exists $y$ such that $Ay^k/p(z_0)$ is a negative real number. For such $y,$ we have $A(ys)^k/p(z_0)<0$ for all $s>0.$ Now there exists (small ) $s>0$ such that $$A(ys)^k=-tP(z_0)\text { for some } t\in(0,1)$$ $$\text { and }\quad |ys\cdot q(ys)|<1/2$$ . $$\text {Then }\quad |p(z_0+ys)|=|(1-t)p(z_0)-tp(z_0)(ys\cdot q(ys)|\leq$$ $$ \leq (1-t)|p(z_0)|+t|p(z_0)|/2=$$ $$=(1-t/2)|p(z_0)|<|p(z_0)|$$ contrary to the minimality of $|p(z_0)|.$
The long list of preliminaries was to ensure that AC hadn't been assumed somewhere.
Best Answer
Yes, both options are valid, with the latter one may be more confusing to people less familiar with the von Neumann hierarchy. You can also start by well-ordering $F_0[x]$, then always adding the necessarily elements as the smallest ordinals not already in your current field.
Since from the well-ordering of $F_0[x]$ (which includes a copy of $F_0$ as the constant "polynomials") we can compute a well-ordering of any single-step extension, we can compute a fairly-canonical well-ordered algebraic closure.
(Once again, transfinite recursion and sets of ordinals win the day.)
Usually, however, we don't really worry about that. To the extent that showing this much effort will often elicit some odd looks from people.