@YCor: I managed to find an $\text{Alt}_4$ example directly: Consider the group (of order $2^7\cdot 7$) given as the semidirect product of the elementary abelian group $E=(C_2)^6 = \mathbf{F}_8\times \mathbf{F}_8$ and $Q=C_{14} =C_2\times C_7$, where $Q$ acts on $E$ by letting $C_2$ swap the two copies of $\mathbf{F}_8$ and letting $C_7=\mathbf{F}_8^*$ act diagonally.

@YCor: Hmmh, I get $\text{Out}(G)\cong \text{Sym}(4)$ when I enter this into Magma. The code is a little too long to enter here but I will send it to you. Just to be sure, what is your notation for commutators : $[x,y]=x^{-1}*y^{-1}*x*y$ (group theorist commutators) or $[x,y]=x*y*x^{-1}*y^{-1}$ (topologist commutators)? I dont think it matters in this case though.

@MikkoKorhonen: Thanks for this. I remember the exercise $\text{Inn}(G)\not\cong Q_8$ ($G$ finite) from an old algebra course. I spent a lot of time searching the litterature and found the same reference as you but I came up emptyhanded searching for the (non)existence of a finite $G$ with $\text{Out}(G)\cong Q_8$. Now it seems that YCor has solved the question in the positive, see his answer below.

@MikkoKorhonen: Is it known that there are no finite groups $G$ with $\text{Out}(G)\cong Q_8$ or is that an open problem?

Can anyone give a precise reference to the Carlson-Thevenaz paper (I didn't manage to find it in there)? Another question: Isn't $P=\mathbb{Z}/4\times \mathbb{Z}/4$, $E=\mathbb{Z}/2\times \mathbb{Z}/2$ a counterexample?

For $2$-groups the first failures are given by $D_{16}$, $SD_{16}$ and another group of order $16$ (no 3 in the SmallGroup library). The first 2 groups contains a $C_2\times C_2$ subgroup (but no normal ones) and the second has a $C_4$-sunbgroup (but no normal ones). For order $32$ the property fails for $24$ out of $51$ groups and for order $64$ it fails for $205$ out of $267$ groups.

Actually Gupta proves that the number of solutions goes to infinity with $n$, see Hansraj Gupta, The American Mathematical Monthly, Vol. 57, No. 5 (May, 1950), pp. 326-329.

Not an answer, just a comment: The result that a nonnegative univariate polynomial is a sum of two squares is a direct consequence of the fundamental theorem of algebra. The result by Polya and Szegö is more subtle, it deals with polynomials on $[0,\infty[$.

The sequence of n's such that $F_n$ is prime is in OEIS: oeis.org/A001605 which also has references.