It seems to me that such an automorphism always exists.
$G$ is minimal non-abelian, see e.g. Proposition 1.5 of this paper by Janko for the classification. (Added: this is not necessarily true, please stand by for a fix.)
Appealing to the classification, and since, by the assumption on the centre, the group $G$ is not quaternion of order 8, we have two cases,
- $G = \langle a, b : a^{2^m} = b^{2^n} = 1, [a, b] = a^{2^{m-1}} \rangle$,
- $G = \langle a, b, c : a^{2^m} = b^{2^n} = c^2 = 1, [a, b] = c, [a, c] = [b, c] = 1 \rangle$.
The centre of $G$ is $\langle a^2 \rangle \times \langle b^2 \rangle$ in the first case, and $\langle a^2 \rangle \times \langle b^2 \rangle \times \langle c \rangle$ in the second case.
Given the assumption on the exponent of $Z(G)$, in the second case we may assume without loss of generality that $m \ge 3$. Then $a \mapsto a^3, b \mapsto b$ defines an automorphism as requested.
In the first case, we have to distinguish two cases. If $m \ge 3$, then $a \mapsto a^3, b \mapsto b$ will do. If $n \ge 3$, then $a \mapsto a, b \mapsto b^3$ will do.