OK, I have a proof which meets your conditions. I relied on this write up of the standard proof as a reference.
Lemma 1: Let $K/F$ be an extension of fields, and let $f(x)$ and $g(x)$ be polynomials in $F[x]$. Let $d_F(x)$ be the GCD of $f$ and $g$ in $F[x]$ and let $d_K(x)$ be the GCD of $f$ and $g$ in $K[x]$. Then $d_F(x)$ and $d_K(x)$ coincide up to a scalar factor.
Proof: Since $d_F(x)|f(x)$ and $d_F(x)|g(x)$ in $K[x]$, we have $d_F(x)|d_K(x)$. Now, there are polynomials $p(x)$ and $q(x)$ in $F[x]$ such that $f(x) p(x) + g(x) q(x) = d_F(x)$. So $d_K(x) | d_F(X)$. Since $d_F(x)$ and $d_K(x)$ divide each other, they only differ by a scalar factor.
Lemma 2: Let $f(x)$ and $g(x)$ be polynomials with $g(0) \neq 0$. Then, for all but finitely many $t$, the polynomials $f(tx)$ and $g(x)$ have no common factor.
Proof: Let $f(x) = f_m x^m + \cdots + f_1 x + f_0$ and $g(x) = g_n x^n + \cdots + g_1 x + g_0$. If $f(tx)$ and $g(x)$ HAVE a nontrivial common factor, then there are polynomials $p(x)$ and $q(x)$, of degrees $\leq n-1$ and $\leq m-1$, such that
$$f(tx) p(x)=g(tx) q(x).$$
This is $m+n$ linear equations on the $m+n$ coefficients of $p$ and $q$.
Writing this out in coefficients, the matrix
$$\begin{pmatrix}
f_m t^m & \cdots & f_1 t & f_0 & 0 & 0 & \cdots & 0 \\
0 & f_m t^m & \cdots & f_1 t & f_0 & 0 & \cdots & 0 \\
\ddots \\
0 & 0 & \cdots & 0 & f_m t^m & \cdots & f_1 t & f_0 \\
g_n & \cdots & g_1 & g_0 & 0 & 0 & \cdots & 0 \\
0 & g_n & \cdots & g_1 & g_0 & 0 & \cdots & 0 \\
\ddots \\
0 & 0 & \cdots & 0 & g_n & \cdots & g_1 & g_0
\end{pmatrix}$$
has nontrivial kernel. The determinant of this matrix is a polynomial in $t$, with leading term $(f_m)^n (g_0)^n t^{mn} + \cdots$. (Recall that $g_0 \neq 0$.) So, for all but finitely many $t$, this matrix has nonzero determinant and $f(tx)$ and $g(x)$ are relatively prime. QED.
Now, we prove the primitive element theorem (for infinite fields). Let $\alpha$ and $\beta$, in $K$, be algebraic and separable over $F$, with minimal polynomials $f$ and $g$. We will show that, for all but finitely many $t$ in $F$, we have $F(\alpha - t \beta) = F(\alpha, \beta)$.
Let $f(x) = (x -\alpha) f'(x -\alpha)$ and $g(x) = (x - \beta) g'(x - \beta)$. Since $\beta$ is separable, we know that $g'(0) \neq 0$. Note that $f'$ and $g'$ have coefficients in $K$. By Lemma 2, for all but infinitely many $t$ in $F$, the polynomials $f'(ty)$ and $g'(y)$ have no common factor. Choose a $t$ for which no common factor exists. Set $F' = F(\alpha - t \beta)$; our goal is to show that $F'=F(\alpha, \beta)$.
Set $h_t(x) = f(tx + \alpha-t \beta)$. Note that $h_t(x)$ has coefficients in $F'$. We consider the GCD of $h_t(x)$ and $g(x)$.
Working in $K$, we can write $h_t(x) = t (x - \beta) f'(t (x- \beta))$ and $g(x) = (x-\beta) g'(x-\beta)$. By the choice of $t$, the polynomials $f'(t (x- \beta))$ and $g'(x-\beta)$ have no common factor, so the GCD of $h_t(x)$ and $g(x)$, in the ring $K[x]$, is $x-\beta$.
By Lemma 1, this shows that $x - \beta$ is in the ring $F'[x]$. In particular, $\beta$ is in $F'$. Clearly, $\alpha$ is then also in $F'$, as $\alpha= (\alpha - t \beta) + t \beta$. We have never written down an element of any field larger than $K$. QED.
Best Answer
Let $F$ be a finite field with $p$ elements. Let $K=F(x,y)$ be the field of rational functions in two indeterminate variables over $F$. Consider the extension of $K$ obtained by adjoining $p$-th roots of $x$ and of $y$. More precisely, let $k$ be an algebraic closure of $K$. In $k$ we can solve the equation $X^p=x$ in the variable $X$. Let $a$ be a solution of this equation; so $a$ is an element of $k$ which satisfies $a^p=x$. Similarly find an element $b$ which satisfies $b^p=y$.
Consider $L=K(a,b)$. $L$ is a finite extension of $K$, of order $p^2 $ as you can check. However there is no element of degree $p^2$ in $L$, and a primitive element would have to have degree $p^2$.
This example is, in a sense, the simplest possible. Separable finite extensions are simple (contain a primitive element), so we must use a non-perfect base field. Also, extensions of degree $p$ are also simple, so we must use $p^2$.