If $|G|=p^2$, $p$ prime and $G$ is not cyslic $G\cong \Bbb Z/p\Bbb Z\times \Bbb Z/p\Bbb Z $ Here is an incomplete proof:
If $H\le G$ is a subgroup, there are only three possibilities for its cardinal: $1,p$ or $p^2$ by Lagrange.
If $|H|=p^2$ then there exists $g\in H\subset G$ of order $p^2$ and so $G$ is cyclic.
If $|H|=1$ and there is no other proper subgroup then $G$ is cyclic.
So there must be a subgroup of order $p$, let $|H|=p$. Let $x$ be in $G$. We will show that $xHx^{-1}=H$ and so $H\triangleleft G.$ By contradiction let's suppose $xHx^{-1}\ne H$. 
$xHx^{-1}$ is a subgroup of $G$ because $$(xhx^{-1})^{-1}=xhx^{-1}\in xHx^{-1} \text{ and }~ xhx^{-1}xh'x^{-1}=xhh'x^{-1}\in xHx^{-1}~\forall h,h'\in xHx^{-1}$$
There is a formula for the cardinality of a product of groups that says $$\begin{align}|xHx^{-1}|\cdot|H|&=  |xHx^{-1}H|\cdot|xHx^{-1}\cap H|\\ |(xHx^{-1})H| &= \frac{|xHx^{-1}|\cdot|H|}{|xHx^{-1}\cap H|}=\frac{p\cdot p}{1}\end{align}$$
And here I'm not sure how to show that $xHx^{-1}$ has cardinality $p$, I guess for the same reason as $H$.
And why is the intersection trivial?
If the equality above is true we get that $xHx^{-1}H=G$ so for any $x\notin H$ there exist some $h_1,h_2\in H$ such that $x=xh_1x^{-1}h_2$
$$\begin{align}e &=h_1x^{-1}h_2\\ h_1^{-1}&= x^{-1}h_2\\ h_1^{-1}h_2^{-1}&= x^{-1}\implies x\in H \text{ (impossible)}\end{align}$$
Once we arrive at a contradiction we have that $xHx^{-1}=H$ so $H$ is normal in $G$.
Then I have to show that there exists $K\le G$ such that $K\cap H=\{e\}$ and $K\triangleleft G$ and from this it will be easy to show that $G\cong K\times H$

What is $H$? Define your variables! I assume that what you mean is something along the lines of: take any non-identity element $h$ of $G$, and let $H$ be the subgroup that it generates. 
This subgroup is cyclic, so cannot be all of $G$, as $G$ is not cyclic, and is not trivial, as it contains $h$, so must have order $p$. 
Now take any $g \in G\setminus H$. Then $\langle g, h\rangle$ contains $H$, but is strictly larger than it, and is a subgroup of $G$, so must be all of $G$. Thus, $G$ is generated by $g$ and $h$. Now, the order of $g$ must also be $p$ (it must divide $p^2$, can't be $1$ since $g$ is not the identity, and can't be $p^2$ since $G$ is not cyclic). Let $K$ be the subgroup generated by $g$. Since $H$ and $K$ both have order $p$ and don't coincide, their intersection must be trivial. Thus, we merely need to show that both are normal in $G$. But given that we chose $H$ to be an arbitrary order-$p$ subgroup, it suffices to show it for $H$.
This follows from your argument: $y \mapsto xyx^{-1}$ is injective (if $xyx^{-1} = xzx^{-1}$, then multiplying that equation by $x^{-1}$ on the left and $x$ on the right gives $y = z$), and is surjective when restricted to map from $H$ to $xHx^{-1}$ by definition of the latter, so $|xHx^{-1}| = |H| = p$. The intersection is trivial since it's a subgroup of $H$, so  has order $1$ or $p$, but isn't all of $H$, so can't have order $p$. 
Thus, $H$ and $K$ are normal, and $G = H \times K$.
