A finite group such that every element is conjugate to its square is trivial

As you say, $G$ must have odd order. Let $p$ be the smallest prime factor of the order of $G$, and $a$ an element of order $p$. Let $H$ be the subgroup generated by $a$, $C$ be the centraliser of $H$ and $N$ the normaliser of $H$. Then $r=|N:C|$ is the number of elements of $H$ which are conjugates of $a$. So $r<p$ but $r>1$, as $a^2\ne a$ is the conjugate of $a$. But $r\mid |G|$ and $1<r<p$, contradicting $p$ being the smallest (prime) factor of $|G|$.

Just to add to Lord Shark's answer, if you are curious, see Lemma 5.1 of the paper Gabriel Navarro, The McKay conjecture and Galois automorphisms, Annals of Mathematics, 160 (2004), 1129–1140.