@SeanEberhard I'm sorry, there is a typo in the question - $H<K$ should have been $H\leq K$. (This also contradict my above claim that "All containments are proper"!) So for $H=\langle x, x^y\rangle$ I want to take $K=H$.

@YCor All containments are proper; I've replaced the $\lneq$ with $<$ to make it uniform.

I did wonder if that was what you meant! It is clearer now.

This is great! However, it seems you are taking an immersion and noting that it corresponds to the basis? A key part of Stallings' paper is his "folding" algorithm, which lets you go the other way - start with a set of words and construct an immersion. From here one can answer the question.

Sorry, yes, you're right - $\pi_1$ of this space corresponds to the subgroup, and as it is a $1$-complex there can only be finitely many loops! I've deleted my comment....

@YCor In this context, any restriction on the number of generators is irrelevant: malnormality is transitive, and any non-abelian countable free group contains malnormal subgroups of arbitrary rank (including infinite).

@Carl-FredrikNybergBrodda For a first example: Enumerate all triangle groups, then take their free product. You can then get a finitely presented example by embedding this group into a finitely presented group via Higman's embedding theorem.

@Carl-FredrikNybergBrodda Yes, my comment is about the most general situation possible, and certainly does not answer the question!

As a specific proof of undecidability in general: let $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ have undecidable word problem, and consider the group $H$ with presentation $\langle \mathbf{x}, y, t\mid\mathbf{r}, t^{-1}yt=yw(\mathbf{x})\rangle$, which is an HNN-extension of $G\ast\mathbb{Z}$. Here, the normaliser of $y$ in $H$ is $\langle y\rangle$ if $w(\mathbf{x})\neq1$ in $G$, and is $\langle y, t\rangle$ if $w(\mathbf{x})=1$ in $G$. As we cannot determine in general if $w(\mathbf{x})=1$, determining the normaliser is also undecidable.

I remember watching this during my PhD! It has stuck with me ever since because it is the only BBC documentary I have ever watched where someone actually proves something on a blackboard.

I'm unsure if GeoGebra needs to be cite like you suggest - see for example this question on academia.SE.