Here's another method without using Euler's totient function or induction. We rely on a lemma:
If $H$ and $K$ are normal subgroups of $G$ such that $H\cap K=\{e\}$, then $\forall x\in H\;\forall y\in K(xy=yx)$
Let $G$ satisfy the above conditions, and let's denote its order by $k$. Then since $G$ is finite, we can find an element of maximal order. Let's pick one of these elements and call it $x$, and let's call its order $n$. If $n=k$, we would be finished as then $G=\langle x\rangle$.
Suppose for contradiction that $k\neq n$. Then there is an element $y\in G\setminus \langle x\rangle$. Let's denote $y$'s order by $m$, and let's choose $y$ to have minimal order among the elements of $G\setminus\langle x\rangle$. By counting arguments, we have that $\langle x\rangle=\{z\in G: z^n=e\}$. We will use $x$ and $y$ to create a new element $z$ which satisfies $z^n=e$ which is not in $\langle x\rangle$ contradicting our assumption.
Consider a conjugate subgroup of $\langle x\rangle$. Such a subgroup would also be cyclic of order $n$, and thus have elements which solve $z^n=e$. Thus there cannot be a distinct conjugate subgroup of $\langle x\rangle$ else we would have too many elements satisfying $z^n=e$. Likewise, $\langle y\rangle$ has no non-trivial conjugate subgroups. This means that $\langle x\rangle$ and $\langle y\rangle$ are normal. Now we consider two subcases:
Case 1: $\gcd(m,n)=1$
In this case, we have that $\langle x\rangle\cap\langle y\rangle=\{e\}$. Thus, we have that all powers of $x$ and $y$ commute. And looking at the element $xy$ gives us an element of order $\text{lcm}(m,n)$. Since in general, $\text{lcm}(m,n)\geq n$ for any $m$, we can conclude $\text{lcm}(m,n)=n$ since $n$ was the maximal order. Further, $xy\not\in\langle x\rangle$ for otherwise that would imply that $y\in\langle x\rangle$. Thus there is another solution to $z^n=e$. A contradiction.
Case 2: $\gcd(m,n)>1$.
Let $d=\gcd(m,n)$. Consider the element $y^{m/d}$. It has order $d$. In general $d=\gcd(m,n)\leq m$. So that $y^{m/d}$ has order less than or equal to $m$. Since $m$ was chosen so as to be minimal, we have $m=d$. Thus we have that $m\mid n$. But this means that $y^n=e$. And thus there is another solution to $z^n=1$. A contradiction.
Thus we must have that $k=n$. That is, $G$ is cyclic.