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.
The Galois group of $F/\mathbb Q$ is cyclic of order $6$ as you described above, and if $\sigma$ is a generator for this group, then since the unique subgroup of order $2$ is $\{1, \sigma^2, \sigma^4 \}$, we can assume without loss of generality that $\sigma^2 = u$. If you compute $\sigma$, you can compute $\sigma^2$ and explicit $E$ as the fixed field of $\sigma^2$.
Now the extension $F/\mathbb Q$ is simple, so $\sigma$ is characterized entirely by where it maps $f$ (let me write $f = \zeta_7$ for clarity). It suffices to find a primitive root of $(\mathbb Z/7\mathbb Z)^{\times}$ and we got it. After some testing you realize that $3^6 = 1$ but $3^2, 3^3 \neq 1 \pmod 7$, so $3$ is a primitive root. This means that $\sigma(\zeta_7) = \zeta_7^3$ is a possibility for $\sigma$ as a generator of the Galois group.
Now $\sigma^2(\zeta_7) = \zeta_7^9 = \zeta_7^2$ (as promised by $\sigma^2 = u$ and $u(f) = f^2$), so we're trying to find the fixed field corresponding to the group $\{ 1,\sigma^2,\sigma^4\}$.
Because of the simple relation $\zeta_7^7 = 1$, it is not hard to solve the equation $\sigma^2(x)-x = 0$ for $x \in F$ ; write
$$
x = a_0 + a_1 \zeta_7 + \cdots + a_5 \zeta_7^5
$$
and apply $\sigma^2$ to it ; the equation $\sigma^2(x) = x$ will give you linear conditions on the coefficients. I'm afraid finding generators involves linear algebra. If you have the patience of writing down the equation by hand, you'll see the computations do not require any smart-ideas and you get
$$
E = \mathbb Q(\zeta_7 + \zeta_7^2 + \zeta_7^4).
$$
The minimal polynomial can be computed, it is
$$
(X - (\zeta_7 + \zeta_7^2 + \zeta_7^4))(X - (\zeta_7^3 + \zeta_7^5 + \zeta_7^6)) = X^2 + X + 2.
$$
The roots of this polynomial are $\frac{-1 \pm \sqrt{-7}}2$, so you can write
$$
E = \mathbb Q(\sqrt{-7}).
$$
Note : The magical reason why I get only one canonical element (i.e. $\zeta_7 + \zeta_7^2 + \zeta_7^4$) as a generator for $E/\mathbb Q$ is because $[E:\mathbb Q] = 2$, so I know the extension can only be generated by one element and that a basis for $E/\mathbb Q$ will be given by $\{1,x\}$ for some $x \in E$. This means when I tried to compute the fixed field of $\sigma^2$, I know the term for $1$ would be irrelevant and the rest would only give me one term.
Interesting remark : You know that $\mathbb Z / 6 \mathbb Z$ has only one subgroup of index $2$ and that the extension $F/\mathbb Q$ is Galois, so by the Galois correspondence $F$ has only one subfield of order $2$ over $\mathbb Q$. The element $\zeta_7 + \sigma^2(\zeta_7) + \sigma^4(\zeta_7)$ is invariant by $\sigma^2$ and is not in $\mathbb Q$, so you could've skipped the linear algebra computations and know already that $E = \mathbb Q(\zeta_7 + \zeta_7^2 + \zeta_7^4)$. We don't escape the computation of the minimal polynomial to simplify this though. (These ideas of averaging are often used in invariant theory ; I averaged the orbit of $\zeta_7$ over the subgroup $\{1,\sigma^2,\sigma^4\}$ to find the invariant substructure I wanted.)
Hope that helps,
Best Answer
Yes, this is always possible. First note that the automorphism of $F$ induces and injective field homomorphism $F\to F(\zeta_{n})$. Then write $F(\zeta_{n})\cong F[T]/(f)$, where $f$ is the minimal polynomial of $\zeta_{n}$. By the universal property of the polynomial ring and of the quotient, sending the class of the variable $T$ to any root of $f$ in the right hand side gives you the desired automorphism of $F(\zeta_{n})$. The result is bijective because it is an injective homomorphism of $F$-vector spaces of the same finite dimension.