This is known as Primitive Element Theorem, stated for reference (Lang's Algebra; V.4. Theorem 4.6, page 243):
Let $E$ be a finite extension of a field $k$. There exists $\alpha\in E$ such that $E=k(\alpha)$ iff there are finite number of fields $k\subset F\subset E$.
Where is the fact that $E=k(\alpha)$ used in $\Rightarrow$ of proof? In other words, where will the proof fail if this isn't the case? I just cannot see it.
Ignoring this assumption, take arbitrary $\alpha \in E$ and nested field $F$. There always exists irreducible polynomial of $\alpha$ over $F$: $g_F(X)$ and $g_F | Irr(\alpha, k, X)$. There are always only finite number of these polynomials (since we have unique factorization in $E^a[X]$), so we always have a mapping: $$F\rightarrow g_F$$
We can always generate subfield $F_0$ by coefficients of $g_F$ and this $\alpha$ is irreducible over $F_0$ and so $F=F_0$, whence mapping is injective.
The gap is in the proof of $F_0=F$. Clearly $F_0\subseteq F$. To prove the opposite inclusion, namely $F\subseteq F_0$ we have $$[F_0(\alpha):F_0]\leq\deg(g_F)=[F(\alpha):F]$$ If $E=k(\alpha)$, then $F_0(\alpha)=E=F(\alpha)$, hence we can conclude $F=F_0$.