Let $F$ be any field. The compositum of separable extensions of $F$ contained in the algebraic closure $\overline{F}$ of $F$ will itself be separable, and so there is a largest separable extension of $F$ contained in $\overline{F}$ (namely, the compositum of all separable extensions). This is called the separable closure of $F$ in $\overline{F}$. (See for example Lang's Algebra, revised 3rd Edition, Theorem 4.5 and discussion following, pp. 241f).
Now start with a non-perfect field; for example, take $\mathbb{F}_p(x)$, the field of rational functions with coefficients in the field of $p$ elements.
Let $K$ be the separable closure of $F$ as above; because $F$ is not perfect, $K$ cannot equal $\overline{F}$. In particular, $K$ is not algebraically closed.
However, every nontrivial algebraic extension of $K$ is not separable (in fact, it will be purely inseparable): because if $L$ is an algebraic separable extension of $K$, then $L$ is also an algebraic separable extension of $F$, hence must be contained in $K$, so $L=K$.
Thus, no nontrivial algebraic extension of $K$ is separable, so no nontrivial algebraic extension of $K$ is Galois over $K$; and yet there are nontrivial algebraic extensions of $K$, since $K$ is not algebraically closed.
As has been mentioned, the result is a direct consequence of the fact that $[\mathbf{Q}(2^{1/n}):\mathbf{Q}]$ = n. This is because we then have, for every $n$, the inequality
$$n = [\mathbf{Q}(2^{1/n}):\mathbf{Q}] \leq [K:\mathbf{Q}].$$
Since $[K:\mathbf{Q}]$ is larger than every natural number, it must be infinite.
The trickiest point is why $2^{1/n}$ has degree $n$ over $\mathbf{Q}$. For this it is enough to establish that the polynomial $X^n - 2$ is irreducible. This follows immediately from Eisenstein's criterion for the prime $p = 2$.
There is an error in your proof that every element of $K$ is algebraic over $\mathbf{Q}$. It is not clear at all why you claim any $\alpha \in K$ can be written in the form of a linear combination of various roots of $2$. The only thing that is obvious is that $\alpha$ can be written as a polynomial expression of these numbers, not a linear combination.
The proof that $K$ is algebraic is as follows. The field $K$ is generated by the set $S = \mathbf{Q} \cup \{2^{1/2}, 2^{1/3}, \dots\} \subseteq \overline{\mathbf{Q}}$, where $\overline{\mathbf{Q}}$ is the field of algebraic numbers over $\mathbf{Q}$. It follows that $K$ itself is contained in $\overline{\mathbf{Q}}$. Thus $K$ is algebraic over $\mathbf{Q}$.
Best Answer
Another simple example is the extension obtained by adjoining all roots of unity.
Since adjoining a primitive $n$-th root of unity gives you an extension of degree $\varphi(n)$ and $\varphi(n)=n-1$ when $n$ is prime, you get algebraic numbers of arbitrarily large degree when you adjoin all roots of unity.