It might be worth noting that you do need $G$ to be finite; otherwise, the claim is not true. For example, the Prüfer $p$-group has the property that given any two elements $a$ and $b$, either $\langle a\rangle \subseteq \langle b\rangle $ or $\langle b\rangle \subseteq \langle a\rangle$, but the group itself is not cyclic.
So, we want to prove:
Suppose $G$ is a finite group such that for all $a,b\in G$, either $\langle a\rangle\subseteq \langle b\rangle$ or else $\langle b\rangle \subseteq \langle a\rangle$. Then $G$ is cyclic.
Your "I think this works" is very badly phrased. You cannot begin by assuming that $G=\langle g\rangle$, because this is tantamount to assuming that $G$ is cyclic; but this is what you want to prove! You don't get to assume it to begin with. At best, you should say: "If $G=\langle g\rangle$, then we're done; otherwise, let..."
The argument works reasonably well: suppose $G=\{g_1,\ldots,g_n\}$ (remember, $G$ has to be finite). Let $a_1=g_1$. Now, consider $g_2$; either $g_2\in\langle a\rangle$ or $\langle a\rangle\subseteq \langle g_2\rangle$. In the former case, let $a_2=g_1$; in the latter, let $a_2=g_2$.
Assume you have already defined $a_1,\ldots,a_{\ell}$, with $1\leq \ell\lt n$. Consider $g_{\ell+1}$. If $g_{\ell+1}\in\langle a_{\ell}\rangle$, let $a_{\ell+1}=a_{\ell}$. Otherwise, we have $\langle a_{\ell}\rangle \subseteq \langle g_{\ell+1}\rangle$; then set $a_{\ell+1}=g_{\ell+1}$.
Now, I claim that $G=\langle a_{n}\rangle$. Indeed, note that by construction, $g_k\in\langle a_{k}\rangle\subseteq \langle a_{k+1}\rangle$. Therefore, $g_1,\ldots,g_k\in\langle a_{k}\rangle$. In particular, $G=\{g_1,\ldots,g_n\}\subseteq \langle a_n\rangle \subseteq G$, giving equality. Thus, $G$ is cyclic.
(There are of course easier ways of doing this; but this follows the intuitive idea of your argument, only written up more formally).