Response to the original question:
Such non-abelian groups, that all their proper subgroups are cyclic (and moreover, such that all their proper subgroups are isomorphic to $C_p$ for a fixed prime $p$) actually do exist. Such groups are called Tarski Monster Groups and there are continuum many of them for each prime $p > 10^{75}$ (this fact was proved by Alexander Ol'shansky in 1979).
Response to the comment by @Myridium:
The infinite abelian groups, that all their proper subgroups are cyclic can be described in the following way:
If all proper subgroups of an infinite abelian group $G$ are cyclic, then $G$ is isomorphic either to $C_\infty$ (infinite cyclic), or to $C_{p^\infty}$ (quasicyclic for some prime $p$), or to $\mathbb{Q}_p$ (the subgroup of $\mathbb{Q}_+$, which consists of fractions with powers of a prime $p$ in denominators).
To prove this statement we will need two lemmas:
Lemma 1:
If all proper subgroups of an infinite abelian group $G$ are cyclic, then $G$ is locally cyclic
If $G$ is finitely genersted, then by classification of finitely generated abelian groups it is isomorphic to $C_\infty$.
If $G$ is infinitely generated then all its finitely generated subgroups are proper, and thus cyclic.
Lemma 2:
A group is locally cyclic iff it is a subquotient of $\mathbb{Q}_+$
The complete proof of this fact can be found there
Proof of the main statement:
If $G$ is finitely generated, then it is $C_\infty$
If $G$ is infinitely generated periodic, then it has a quasicyclic subgroup (by classification of locally cyclic groups). And as quasicyclic groups are not cyclic, this subgroup is the whole group.
If $G$ is infinitely generated aperiodic, then its quotient by an infinite cyclic subgroup is infinitely generated periodic and also satisfies the required property. So $G$ is a locally cyclic extension of $C_\infty$ by $C_{p^\infty}$ for some prime $p$, which can be only $\mathbb{Q}_p$.
Best Answer
The simplest possible example of this would be $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$, as this is abelian and is the smallest group which is not cyclic. It is also known as the Klein four-group.