Well, this is an exercise problem from Herstein which sounds difficult:
The only thing I know which connects a group with its automorphism is the theorem, $$G/Z(G) \cong \mathcal{I}(G)$$ where $\mathcal{I}(G)$ denotes the Inner- Automorphism group of $G$. So for a group with $Z(G)=(e)$, we can conclude that it has a non-trivial automorphism, but what about groups with center?
On
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.
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$.