Finding the structure of a group without using sylows theorem.

As Gerry Meyerson pointed out, it does not hold in general as it is stated. You need to infer that $p \lt q$. Choose $Q$ a subgroup of $G$ of order $q$ (you can use Cauchy's Theorem for its existence!). Then $|G:Q|=p$ is the smallest prime dividing $|G|$ (ah yes here we are using $p \lt q$), hence $Q \lhd G$ (I hope you know this theorem ... see here for example).

Now $P$ acts on $Q$ by conjugation, but since $p \nmid q-1$ and Aut$(Q) \cong C_{q-1}$ (here we use that $q$ is prime), the action must be trivial: $P$ centralizes $Q$ and the other way around. Since $G=PQ$, $G$ must be abelian and the Chinese Remainder Theorem does the rest: $G \cong C_p \times C_q \cong C_{pq}$.

Bonus remark if $|G|=n$ and gcd$(\varphi(n),n)=1$, then $G$ is cyclic (as a matter of fact the only group of order $n$).

An argument close to the OP's idea could proceed as follows. Fill in the details.

1. If $x$ and $y$ are elements of order $q$, then among the products $x^iy^j$, $0\le i,j<q$, there must be repetitions. This is because $q^2>|G|$. Show that this implies that the subgroup $H$ of order $q$ is unique. Let's fix a generator $x$ of $H$.
2. If $z\notin H$ has order $pq$ then $G$ is cyclic. Therefore the remaining possibility is that all such elements $z$ have order $p$.
3. Because $H$ is a unique subgroup of its order, $H\unlhd G$. Why does it follow that $zxz^{-1}=x^i$ for some $i, 1\le i<q$?
4. Why do we have $z^pxz^{-p}=x$?
5. On the other hand we also have $z^pxz^{-p}=x^{i^p}$, why? Why does this imply the congruence $$i^p\equiv1\pmod q?$$
6. It follows that the coset of $i$ in the multiplicative group $\Bbb{Z}_q^*$ has either order $1$ or order $p$. Why?
7. If the order of the coset of $i$ is equal to one, then $zx$ has order $pq$. Why?
8. If the order of the coset of $i$ is equal to $p$, why does it follow that $p\mid q-1$?