Update My previous proof was incorrect. This updated proof is inspired by the comment by 'MartianInvader'.
Problem I can prove the statement 'Every algebraic extension $L:K$ has a normal closure $F:L$' by taking an algebraic closure $\bar{L}$ of $L$ (existence needs AC), and letting $F = L(S)$ where $S$ is the set of $\alpha \in \bar{L}$ whose minimal polynomial over $K$ is precisely that of some $\beta \in L$. The $F$ produced this way is normal because it is a splitting field extension of the set of minimal polynomials of $\alpha \in L$ over $K$.
The question is: Is there a proof without taking the algebraic closure?
Note $F:L$ is called a normal closure of an algebraic extension $L:K$ if $F:K$ is normal (meaning it is algebraic and the minimal polynomial of any $\alpha \in F$ over $K$ splits) and there are no intermediate fields $M$ between $F,L$ such that $M:K$ is normal (so $F$ is the 'smallest' such).
Also, an extension $F:K$ is normal iff it is a splitting field extension of some subset of $K[x]$.