The first thing I would do is to reduce to abelian $p$-groups: If $A = G_1 \times \cdots \times G_r$ where each $G_i$ is a $p_i$-Sylow subgroup of $A$, then every subgroup $B$ of $A$ is a product of subgroups $B_i$ of $G_i$'s. (in fact $B_i$ will be the $p_i$-Sylow subgroup of $B$.)
So assume $A$ is an abelian $p$-group, say $A=\prod_{i=1}^k (\mathbb{Z}/p^{e_i} \mathbb{Z})^{r_i}$. In this case, clearly every $i$ can contributes up to $r_i$ direct factors of order dividing $p^{e_i}$. I think it is straightforward, although tedious, to show that no other subgroups can occur. (I haven't wrote the details, so one have to check...)
So I think the answer to your question is: YES
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
In general there is no quick way to determine all the normal subgroups. Especially when the groups $G$ get larger you better use a tool like $GAP$, see here. You can always start with the usual suspects: the center of the group $Z(G)$, the commutator subgroup $G'$, etc.. For instance, in the case of $G=Q_8=\{±1,±i,±j,±k\}$, the center equals the commutator subgroup equals $\{-1,1\}$. And if $\{1\} \lneq N \lhd Q_8$, then $|G/N| \leq 4$, hence $G/N$ is abelian and $G' \subseteq N$. This limits your search by hand.