An element is integral iff its minimal polynomial has integral coefficients.
Solution 1:
Sorry I misread your question earlier. Yes all the $\beta_i$ have to be in an algebraic closure $\bar{K}$. This is because $L$ may not be a normal extension of $K$. For an example take $K = \Bbb{Q}$ and $L = \Bbb{Q}(\sqrt[3]{2})$. Then the element $\beta = \sqrt[3]{2}$ has minimal polynomial $x^3 - 2$ but the other two roots are $\zeta_3\sqrt[3]{2}$ and $\zeta_3^2\sqrt[3]{2}$ which don't lie in $L$.
So let us recollect the proof of Neukirch. One direction is already clear so we prove that if $\beta \in L$ is integral over $A$ then its minimal polynomial $p(t) \in A[t]$. Now by assumption because $\beta$ is integral over $A$ we can write down the integral dependence relation given by some $g(t) \in A[t]$ which $\beta$ satisfies. Then $p(t) | g(t)$ and thus every root of $p$ is a root of $g$. Thus every root of $\beta_i$ of $p$ lying in some algebraic closure $\overline{K}$ is integral over $A$.
By Vieta's formulas the coefficients of $p(t)$ are linear combinations of products of the roots. Since the product and sum of two integral elements is integral, we conclude that $p(t)$ actually has coefficients in $A$.