First of all, the group $G$ has to be non-abelian. Otherwise any subgroup is normal and $a^{-1}Ha = H$ for each $a \in G$. You also need the subgroup $H$ (and thus $G$) to be infinite as you mentioned.
I'll give a different example. Let $G = S_{\mathbb{Z}}$, the group of bijections from $\mathbb{Z}$ to $\mathbb{Z}$.
For the subgroup, let $H = \{f \in G \mid f(x) = x \text{ for each } x \leq 0 \}$. Define the map $\sigma \in G$ by $\sigma(x) = x + 1$ for every $x \in \mathbb{Z}$.
It is not difficult to show that $\sigma H\sigma^{-1} \subseteq H$. Since $\sigma f \sigma^{-1}(1) = \sigma(f(0)) = \sigma(0) = 1$ for any $f \in H$, we notice that $\sigma H \sigma^{-1}$ contains only maps that fix $1$. Thus $\sigma H \sigma^{-1}$ cannot be all of $H$.