This is a very nice question! There is a well-known question "if $G$ is qi to $Z^n$ then $G$ is virtually $Z^n$." I've been told that Yehuda Shalom has a proof that avoids using Gromov's theorem - I couldn't find a reference on-line for this.
Here is an idea for a proofan answer to your question. A finitely generated group $G$ has either 0, 1, 2 or infintely infinitely many ends, in the sense of Stallings. Assuming linear growth for $G$ rules out zero and infinity. If $G$ has two ends then Stallings proves that $G$ is virtually cyclic. So we may assume, for a contradiction, that $G$ is one-ended.
Choose a geodesic ray $R \subset G$ that starts at the identity and exits the unique end of the Cayley graph of $G$. (Note that $R$ exists because the Cayley graph is proper - metric balls are compact.) Here is the vague bit; deduce somehow that $G$ is quasi-isometric to $R$. This gives a quasi-action of $G$ on the positive reals. Thus there are group elements $g_n \in G$ act on $R$ essentially via positive translation by $n$. (This is a lie, of course; they may also expand/contract, but only a uniformly bounded amount.) However, for sufficiently large $n$ the element $g_n$ cannot have an inverse in $G$, and we are done.
Here is an idea for a proof. A finitely generated group $G$ has either 0, 1, 2 or infintely many ends, in the sense of Stallings. Assuming linear growth for $G$ rules out zero and infinity. If $G$ has two ends then Stallings proves that $G$ is virtually cyclic. So we may assume, for a contradiction, that $G$ is one-ended.
Choose a geodesic ray $R \subset G$ that starts at the identity and exits the unique end of the Cayley graph of $G$. (Note that $R$ exists because the Cayley graph is proper - metric balls are compact.) Here is the vague bit; deduce somehow that $G$ is quasi-isometric to $R$. This gives a quasi-action of $G$ on the positive reals. Thus there are group elements $g_n \in G$ act on $R$ essentially via positive translation by $n$. (This is a lie, of course; they may also expand/contract, but only a uniformly bounded amount.) However, for sufficiently large $n$ the element $g_n$ cannot have an inverse in $G$, and we are done.