Let $F =$ the free group generated by $\Sigma \cup V$ where $\Sigma = \Sigma(s)$ is the minimal alphabet that $s$ is over, and $V = \{V_1, \dots, V_n\}$ is a finite set of variables.
I would like to quotient by the smallest normal subgroup containing all of $V_i^{-1} v_i$ where $v_i = $ a substring of $s$ or basically a string over $\Sigma$. We've essentially then identified all variables with what they will be expanded to in the course of working out various grammars that generate $\{s\}$.
How would we take the smallest normal subgroup containing all those elements?
Like you said, you've identified all variables $V_i$ with strings in the alphabet $\Sigma$. The quotient by the normal closure of this set of relators is going to be naturally isomorphic with the free group over $\Sigma$, no more and no less.
Usually when you quotient a free group, what you are doing is basically writing down a presentation for your quotient. No one ever wonders what the normal closure of the set of relators looks like, but if this is really what you want, you can say that it is the set of all finite products of conjugates of your relators and their inverses:
$$\bigcup_{m=0}^\infty\left\{\prod_{i=1}^m g_iR_ig_i^{-1}, g_i\in F, R_i\in\mathfrak{R}\right\}$$ with $\mathfrak{R}=\left\{V_1^{-1}v_1,v_1^{-1}V_1,\ldots, V_n^{-1}v_n,v_n^{-1}V_n\right\}$.