I think I managed to prove that, if a finite group $G$ has an automorphism $\varphi$ of order $2$ which doesn't fix any nontrivial elements, then:
- $G$ has odd order;
- $G$ has odd conjugacy classes, and each of them is of odd size;
- $\varphi$ acts on the set of the conjugacy classes of $G$ likewise it acts on $G$ itself, namely it doesn't fix any nontrivial conjugacy class.
This is not surprising, since such a group turns out to be Abelian (see e.g. here and here). I'd expect 1-2-3 to lead to an alternative proof of $G$'s Abelianiness, by obtaining from them that all the conjugacy classes must be singletons. This is where I'm stuck.
Let $G$ be the Heisenberg group mod $p$ for odd prime $p>3$. Then $|G|=p^3$ and $G$ has $p^2-1$ conjugacy classes of size $p$ and $p$ conjugacy classes of size $1$, so $G$ satisfies 1 and 2. Also:
There is a bijection $\varphi : G \to G$ (but not an automorphism) such that $\varphi^2 = \mathrm{id}$ fixing the identity, permuting the conjugacy classes, and not fixing any nontrivial conjugacy class: there are an even number of conjugacy classes of size $p$ and an even number of nontrivial conjugacy classes of size $1$, so there are many ways of doing this.
There is an automorphism $\varphi : G \to G$ (but not satisfying $\varphi^2 = \mathrm{id}$) fixing no nontrivial conjugacy class: take $\varphi$ to be conjugation by a diagonal matrix with entries $a^{-1},1,b$ where $a, b, ab \neq 1$. Then $$ \begin{pmatrix} 1 & x & z \\ 0 & 1 & y \\ 0 & 0 & 1 \end{pmatrix}^\varphi = \begin{pmatrix} 1 & ax & abz \\ 0 & 1 & by \\ 0 & 0 & 1 \end{pmatrix},$$ and it follows from this that no nontrivial conjugacy class is fixed.
And as mentioned in the comment section, if you assume $\varphi$ is both an automorphism and order-2 then $\varphi$ has no nontrivial fixed points so $G$ is abelian.