I assume you mean the group $Q_8$, the 8-element group of quaternions.
Lemma. Let $G$ be a group. Then every cyclic subgroup of $G$ is normal if and only if every subgroup of $G$ is normal.
Proof. Clearly, if every subgroup is normal, then every cyclic subgroup is normal. For the converse, suppose that every cyclic subgroup is normal, and let $H$ be any subgroup of $G$; we must show that $H$ is normal. To show that $H$ is normal, let $h\in H$ and $g\in G$; we must show that $ghg^{-1}\in H$. But $h\in\langle h\rangle$, hence $ghg^{-1}\in g\langle h\rangle g^{-1} = \langle h\rangle\subseteq H$ by our hypothesis that all cyclic subgroups are normal, so $ghg^{-1}\in H$, as desired. Thus, $H\triangleleft G$. $\Box$
So it suffices to show that every cyclic subgroup of $Q_8\times \mathbb{Z}_2$ is normal. Let $(a,b)\in Q_8\times\mathbb{Z}_2$, and let $(x,y)\in Q_8\times\mathbb{Z}_2$ be an arbitrary element of $Q_8\times\mathbb{Z}_2$. We want to show that $(x,y)(a,b)(x,y)^{-1}\in\langle(a,b)\rangle$.
Notice that $(x,y)(a,b)(x,y)^{-1} = (xax^{-1},yby^{-1}) = (xax^{-1},b)$, because $\mathbb{Z}_2$ is abelian. Also, since every subgroup of $Q_8$ is normal, then $xax^{-1}\in\langle a\rangle$.
Now, notice that $xax^{-1} = a^k$ for some $k$, and that $xax^{-1}$ has the same order as $a$ (conjugation is an automorphism). Therefore, $k$ is relatively prime to the order of $a$. Since $|Q_8| = 8$, the order of $a$ is a power of $2$, and we may assume that $k$ is odd.
Therefore, $k=2r+1$ for some $r$, so we have $(x,y)(a,b)(x,y)^{-1} = (xax^{-1},b) = (a^k,b) = (a^{2r+1},b).$
Can you show now that $(x,y)(a,b)(x,y)^{-1}$ lies in $\langle(a,b)\rangle$?
Added. For an encore, prove the "easy half" of Dedekind's characterization of the Hamiltonian groups (nonabelian groups in which every subgroup is normal):
Theorem. If $G=Q_8\times F\times D$, where $F$ is a direct sum of (any number of) copies of $\mathbb{Z}_2$, and $D$ is an abelian group in which every element has (finite) odd order, then every subgroup of $G$ is normal.
Added 2. A few people seem to have jumped to the conclusion that the result follows because every subgroup of $Q_8$ is normal in $Q_8$, and $\mathbb{Z}_2$ is abelian so every subgroup is normal. Intuitively, they are thinking that if every subgroup of $G$ is normal, and every subgroup of $K$ is normal, then every subgroup of $G\times K$ "should" be normal, since conjugation is acting on each coordinate separately. The problem with the argument is that not every subgroup of $G\times K$ is of the form $A\times B$ with $A\leq G$ and $B\leq K$, so while conjugating $(a,b)$ will map $a$ to another element of $\langle a\rangle$, and $b$ to another element of $\langle b\rangle$, this element may not be a power of $(a,b)$.
For instance, $G=Q_8\times Q_8$ already fails to have the property that every subgroup is normal even though each subgroup of each factor is normal in that factor: if $H=\langle (i,i)\rangle$, then $H$ is contained in the diagonal subgroup of $G$, but conjugating by $(j,1)$ moves $(i,i)$ outside the diagonal, so $H$ is not normal. The same problem arises with the counterexample I gave in comments, using $G=Q_8\times\mathbb{Z}_4$ and the subgroup generated by $(i,1)$.