On simple groups $G$, where $2\mid |G|$, $4\not\mid |G|$
It is indeed the only counterexample. Here's how you go about showing that.
Let $|G|=2n$ where $n$ is odd, and let $x\in G$ have order $2$. The permutation $G\to G$ given by multiplication (say on the left) by $x$ is an involution, and yet it fixes nothing. Thus its cycle decomposition is comprised of $n$ $2$-cycles, whence $x$ induces an odd permutation.
The set of elements of $G$ which induce even permutations forms a subgroup $H$. For any $g\in G\setminus H$, we note that $xg$ is an element of $H$, so $g\in x^{-1}H$. This means that the index of $H$ in $G$ is $2$, and and as result $H\lhd G$.
If $|G|>2$, then $H$ is a nontrivial normal subgroup of $G$.
I learned this argument in the text Finite Group Theory by Martin Isaacs, pg. 35, and I have hardly changed it here.
This is a standard result, and the proof -- show that the hypotheses imply that the left action of $G$ on itself does not land in the alternating subgroup $A_{|G|}$ and thus the kernel of the sign homomorphism gives an index $2$ normal subgroup -- is also standard. But I had a hard time remembering it: I would look it up in my undergraduate algebra text every few years. $\newcommand{\ra}{\rightarrow}$
A few months ago though I found a construction which is a bit more general but also more conceptual, and thus I think I will remember it from now on. The idea is that whenever a group $G$ acts on a finite set $X$ we get a homomorphism $G \ra \operatorname{Sym} X$; by composing with the natural sign map $\operatorname{Sym} X \ra \{\pm 1\}$ we get a signature homomorphism $\epsilon_X: G \ra \{ \pm 1\}$. It is interesting to try to determine $\epsilon_X$ for various natural representations: in fact, this is related to Zolotarev's proof of quadratic reciprocity and came up in some work of mine on "abstract" generalizations thereof.
If we start with the group $G$, what is the most natural $G$-set? Certainly it is $G$ acting on itself, say from the left (doing it on the right doesn't change what happens next). I call the associated homomorphism $\epsilon_G: G \ra \{ \pm 1\}$ the Cayley signature map of $G$. It turns out that there is a surprising clean characterization of $\epsilon_G$:
Lemma: Let $G$ be a finite group.
a) The following are equivalent:
(i) The Cayley signature homomorphism $\epsilon_G$ is nontrivial.
(ii) The Sylow $2$-subgroups of $G$ are cyclic and nontrivial.
b) If $\epsilon_G$ is nontrivial, its kernel is the unique index $2$ subgroup of $G$.
I discovered this result for myself and was pleased with it. I found though that part a) previously appeared in a 1979 MONTHLY note of Patrick Morton. For a proof and for further related results, see Lemma 3 here. Part a) is very elementary and comes from the easy identification of the cycle type of $g \cdot$ for any $g \in G$. Part b) uses what I think must be the very first "normal complement theorem", due in this case -- appropriately enough! -- to Cayley. (A reference to Cayley's normal complement theorem seems to be missing currently; maybe someone can help me out here...)
Now let $G$ be finite of order $n \equiv 2 \pmod{4}$. Then its Sylow $2$-subgroups have order $2$, so must be cyclic and nontrivial. It follows that $\epsilon_G$ is nontrivial, and its kernel is a normal, index $2$ subgroup of $G$ (of course index $2$ subgroups of any group are always normal). So $G$ cannot be simple unless it itself has order $2$. Moreover $\operatorname{Ker} \epsilon$ is the unique index $2$ subgroup of order $G$.
As the OP says, this problem is often asked on qualifying exams. In fact algebra quals often ask other problems which can be solved by this technique of extracting an index $2$ subgroup from the Cayley action of $G$ on itself. I think that the above Lemma will help with these as well...