I've just tried to come up with a proof of the above statement but I feel like something is not quite right. The question I have isn't about proving the statement, I've found that in lots of places, but rather about this particular proof.
Firstly we can define a normal subgroup $H$ (of $G$) to satisfy: $$ \forall a\in G \;\forall h\in H\;\;\;\; aha^{-1}\in H $$ This is what I tried: $ \forall a\in G\; aH=Ha $ means that $x\in aH \iff x\in Ha$ so from $x\in aH$: $$ \forall x\in aH\; \exists h\in H :x=ah\; \rightarrow\;xa^{-1}=aha^{-1} (\in H \text{ from below reasoning})$$ where we can show that $xa^{-1}$ is in $H$ using similar logic from the fact that $x$ is also in $Ha$.
The problem I have is I'm wondering whether I've actually shown that the subgroup is normal since the definition of it being normal requires a '$\forall h\in H$' (the $\forall a\in G$ is already in the proof) whereas the way I showed it only found that $h$ exists rather than showing it works for every $h$. I thought maybe it was bound up in $\forall x\in aH$ but I can't seem to concretely get at it. Or maybe there's something wrong with my understanding somewhere (either with the proof writing or group theory).
Added:
I've just been thinking about it a little. If we have $\forall x\in aH \;\exists h\in H:x=ah$ then surely, for a fixed $a$, all of the $h$'s (that correspond to a particular element, $x$, in the coset) must be unique since you can't have two elements equal in the same coset (and since $a$ is fixed it must be the $h$ that's changing). The order of $aH$ is the same as the order of $H$ so that surely means all the $h$'s in $H$ are 'used' in the above proof so it would be $\forall h\in H$ for that fixed $a$ (or another way might be to see the map $H\rightarrow aH$ defined by $h\mapsto ah$ is bijective). Then when you vary $a$ the same reasoning applies so you get the $\forall a\in G\; \forall h \in H $. I know this isn't the most efficient way to prove this, it's more to help my understanding (which hopefully my above reasoning explains why I think it should work) than wanting to prove it.
This is how I understand your question: Suppose we know that $$\forall a \in G\,\forall x \in aH\exists h\in H:x=ah\wedge aha^{-1}\in H\qquad\qquad (*)$$ can we deduce $$\forall a \in G\,\forall h\in H:aha^{-1}\in H.$$ The answer is (of course) yes. Let $a \in G$ and let $h \in H$, then $ah$ is in $aH$ and hence by $(*)$ there exist $h'$ is in $H$ such that $ah=ah'$ and $ah'a^{-1}$ is in $H$, but this means that $h=a^{-1}ah=a^{-1}ah'=h'$ and hence $aha^{-1}$ is in $H$ as desired.