$|G|>2$ implies $G$ has non trivial automorphism

As you note in the question, the group of inner automorphisms Inn($G$) is isomorphic to $G/Z(G)$. In particular, it's trivial if and only if $Z(G)=G$. So there is a non-trivial (inner) automorphism unless $G=Z(G)$.

Now, notice that, by definition, $Z(G)=G$ if and only if $G$ is abelian; so we have reduced to the abelian case.

If $G$ is abelian then $g\mapsto -g$ is an automorphism, and it is non-trivial unless $g=-g$ for all $g\in G$. But $g=-g$ if and only if the order of $g$ divdes two. So we have now reduced to the case in which $2g=0$ for all $g\in G$.

In this case, $G$ is a vector space over the field $\mathbb{Z}/2$. As $|G|$ is equal to 2 raised to the power of the $\mathbb{Z}/2$-dimension of $G$, the hypothesis that $|G|>2$ implies that $\mathrm{dim}_{\mathbb{Z/2}} G>1$. But now we can write down lots of linear automorphisms of $G$. For instance, you could fix any basis $g_1,g_2,\ldots$ and take the automorphism $g_1\mapsto g_2$, $g_2\mapsto g_1$ and $g_i\mapsto g_i$ for every $i>2$.

If $G$ is not abelian, then conjugation by a noncentral element will do.

If $G$ is abelian, then $x\mapsto x^{-1}$ is an automorphism. It will be nontrivial unless every element of $G$ equals its inverse, that is, if every element of $G$ is of exponent $2$.

If every element of $G$ is of exponent $2$, then $G$ is a vector space over the field of $2$ elements, so it is isomorphic to a (possibly infinite) sum of copies of $C_2$, the cyclic group of two elements. Since $|G|\gt 2$, there are at least two copies, so the linear transformation that swaps two copies of $C_2$ is a nontrivial automorphism.

The other two answers assume the axiom of choice:

• Arturo Magidin uses choice when he forms the direct sum ("...it is isomorphic to a (possibly infinite) sum of copies of $C_2$...")
• HJRW uses choice when he fixes a basis (the proof that every vector space has a basis requires the axiom of choice).

If we do not assume the axiom of choice then it is consistent that there exists a group $G$ of order greater than two such that $\operatorname{Aut}(G)$ is trivial. This is explained in this answer of Asaf Karagila.