If the automorphism group is cyclic, then the Inner automorphism group is cyclic. But the inner automorphism group is isomorphic to $G/Z(G)$, and if $G/Z(G)$ is cyclic, then it is trivial. Therefore, $G=Z(G)$ so $G$ is abelian. (The argument does not require $G$ to be finite, by the by.)
For the latter:
Prop. If $H\subseteq Z(G)$ and $G/H$ is cyclic, then $G$ is abelian.
Suppose $G/H$ is cyclic, with $H\subseteq Z(G)$. Let $g\in G$ be such that $gH$ generates $G/H$. Then every $x\in G$ can be written as $x=g^kh$ for some integer $k$ and some $h\in H$. Given $x,y\in G$, we have $x=g^kh$ and $y=g^{\ell}h'$, so
$$\begin{align*}
xy &= (g^kh)(g^{\ell}h')\\
&= g^kg^{\ell}hh' &\quad&\text{since }h\in Z(G)\\
&= g^{\ell}g^kh'h\\
&= g^{\ell}h'g^kh &&\text{since }h'\in Z(G)\\
&= (g^{\ell}h')(g^kh)\\
&= yx,
\end{align*}$$
hence $G$ is abelian. QED
For more on what groups can occur as central quotients, see this previous question.
Added. Since you mention you did not know that $\mathrm{Inn}(G)\cong G/Z(G)$, let's do that too:
Define a map $G\to \mathrm{Aut}(G)$ by mapping $g\mapsto \varphi_g$, where $\varphi_g$ is "conjugation by $g$". That is, for all $x\in G$,
$\varphi_g(x) = gxg^{-1}$.
This map is a group homomorphism: if $g,h\in G$, then we want to show that $\varphi_{gh} = \varphi_g\circ\varphi_h$. To that end, let $x\in G$ be any element, and we show that $\varphi_{gh}(x) = \varphi_g(\varphi_h(x))$.
$$\varphi_{gh}(x) = (gh)x(gh)^{-1} = ghxh^{-1}g^{-1}= g(hxh^{-1})g^{-1} = \varphi_g(hxh^{-1}) = \varphi_g(\varphi_h(x)).$$
Therefore, the map $g\mapsto\varphi_g$ is a homomorphism from $G$ onto $\mathrm{Inn}(G)$. By the Isomorphism Theorem, $\mathrm{Inn}(G)$ is isomorphic to $G/N$, where $N$ is the kernel of this homomorphism.
What is $N$? $g\in N$ if and only if $\varphi_g$ is the identity element of $\mathrm{Aut}(G)$, which is the identity; that is, if and only if $\varphi_g(x)=x$ for all $x\in G$. But $\varphi_g(x)=x$ if and only if $gxg^{-1}=x$, if and only if $gx = xg$. So $\varphi_g(x) = x$ if and only if $g$ commutes with $x$. Thus, $\varphi_g(x)=x$ for all $x$ if and only if $g$ commutes with all $x$, if and only if $g\in Z(G)$. Thus, $N=Z(G)$, so $\mathrm{Inn}(G)\cong G/Z(G)$, as claimed.
Here are some hints:
Let $G$ be a group with a cyclic and odd group of automorphisms.
- Since $G/Z$ (Z being the center) is a subgroup of $\operatorname{Aut} G$, it will be cyclic. Deduce that $G = Z$, i.e. $G$ is abelian.
- Since $G$ is abelian, what can you say about $x\mapsto x^{-1}$ ? Deduce that $G \cong \bigoplus_{i} \mathbb Z/2\mathbb Z$, i.e. $G$ is an elementary abelian $2$-group.
- Now you know a lot about $G$, so you may try to find automorphisms of $G$ that will contradict that $\operatorname{Aut} G$ is cyclic.
I can give more hints if you tell where you're stuck.
-- editted: for step 3: For instance: If there are at least 3 factors involved in the direct product $G \cong \bigoplus_i (\mathbb Z/2\mathbb Z)$ then permuting these factors gives rise to an automorphism (for instance $(a,b,c,...)\mapsto (b,a,c,...)$). This implies $S_3$ appears as subgroup of the automorphism-group so it will surely not be cyclic. If there are $2$ factors $G\cong (\mathbb Z/2\mathbb Z)^2$ and it's easy to see that any permutation of the three involutions of this group is an automorphism.
I think there is a more beautiful way to derive the contradiction but I don't see it right now.
-- editted (much later): I just thought of the more beautiful way: If the direct sum has at least two terms, consider the automorphism that switches these terms $(a,b,c,\dots)\mapsto (b,a,c,\dots)$. This is an automorphism of order 2, a contradiction.
Best Answer
Why would $f^n=\text{id}_G$ imply that every element of $G$ will have finite order? Just because $$f^n(a)=\underbrace{f(f(\cdots f}_{n\text{ times}}(a)))=a$$ does not mean that $a^n=a$.
Hint: An infinite cyclic group is isomorphic to $\mathbb{Z}$. Which individual elements of $\mathbb{Z}$ generate $\mathbb{Z}$? Any group homomorphism $f:\mathbb{Z}\to G$ is determined by what it does to generators. Where can a homomorphism $f:\mathbb{Z}\to\mathbb{Z}$ send a generator if it is to be an automorphism?