We will prove that any such group is the direct product of a quaternion group $Q_8$ and an elementary abelian $2$-group.
As you have shown, $G$ has exponent $4$ (as it cannot have exponent $2$, since such groups are elementary abelian).
Let $g\in G\setminus Z(G)$ have order $2$, and let $h\in G\setminus C_G(g)$. Then $g^2=1$, so $h^2=1$ as well. But $\langle g,h\rangle$ is generated by two involutions and is non-abelian, so must be $D_8$. However, then $gh$ has order $4$ and does not commute with $g$ either, a contradiction.
Thus all involutions are central. Let $g$ and $h$ be non-commuting elements of order $4$, and let $H$ be generated by them. If $x\in C_G(H)$ then $g$ and $hx$ cannot commute either, whence $g^2=(xh)^2=x^2h^2$. Since $g^2=h^2$, we see $x^2=1$, and $C_G(H)$ (and therefore also $Z(G)$) consists of exactly the involutions in $G$.
Notice that $g^4=1$, so $g^{-1}=zg$, where $z=g^2\in Z(G)$. If $[g,h]\neq 1$ then $g^2=h^2=z$, and again $h^{-1}=zh$. Also if $[g,h]\neq 1$ then $[g,gh]\neq 1$, so $(gh)^2=z$. Thus
$$h^{-1}gh=h^3gh=hghz=hghgg=zg=g^{-1}.$$
In particular this means that every cyclic subgroup is normal, since $g^h=g^{\pm 1}$ for all $g,h\in G$.
By assumption the two cyclic subgroups do not commute, thus they generate a $Q_8$ subgroup $H$ (noting that $\langle g\rangle\cap \langle h\rangle=\langle g^2\rangle$ as above). Also, if $X=\langle g\rangle$, then $N_G(X)/C_G(X)$ has order $2$, so $|G:C_G(X)|=2$. By symmetry, the same holds for $Y=\langle h\rangle$.
We aim to show that $G=HZ(G)$. But $C_G(H)=C_G(X)\cap C_G(Y)$ has index at most $4$, whereas $H/Z(H)$ has order $4$, so $G=HC_G(H)$. Since $C_G(H)$ is elementary abelian, $C_G(H)=Z(G)$, so $G=HZ(G)$.
Thus $G=HZ(G)$, $Z(G)$ is elementary abelian, and so $G\cong H\times Z$ for some elementary abelian group $Z$.
