Normal Ordering
The trick is to realise that a normal ordered string of fields is just an Hermite polynomial (ref. $[1]$):
$$
\colon \phi^n\colon=H_n(\phi)\tag{1}
$$
so that, for example,
$$
\colon \phi^2\colon=\phi^2-c\tag{2}
$$
where
$$
c\equiv [\phi^+,\phi^-]=\delta(\boldsymbol 0)\tag{3}
$$
is a (formally divergent) constant.
In the case of free theories, the Hamiltonian is quadratic in $\phi$, and therefore
$$
\colon\mathcal H_\mathrm{free}\colon=\mathcal H_\mathrm{free}-c\tag{4}
$$
which implies that $c$ is just the zero-point energy. In a more general theory, we have
$$
\colon\mathcal H\colon=\mathcal H+P(\phi),\tag{5}
$$
where $P(\phi)$ is just a polynomial in $\phi$. Therefore, the normal-ordered and the non-normal-ordered theories are qualitatively identical.
For example, in the case of $\phi^3$ theory,
$$
\colon\phi^3\colon=\phi^3-3c\phi\tag{6}
$$
which implies that the interactions $\colon\phi^3\colon$ and $\phi^3$ give rise to the same theories modulo tadpoles.
Similarly, in $\phi^4$ theory,
$$
\colon\phi^4\colon=\phi^4-6c\phi^2+3c^2 \tag{7}
$$
which implies that $\colon\phi^4\colon$ and $\phi^4$ give rise to the same theories modulo a mass renormalisation (known as slugs), and an inconsequential zero-point energy (that only affects vacuum bubbles).
Higher-order interactions are not considered because of renormalisability, but the discussion is analogous. In a nutshell, normal ordering a Lagrangian leaves invariant the higher order term, and modifies the coefficient of the rest of the terms. This implies that the normal ordered and the non-normal ordered theories only differ in the value of the counter-terms.
In the case of gauge theories, the problem is slightly more subtle, because normal ordering may affect the Ward identity. The case of QED is particularly simple because here (cf. $[2]$)
$$
\colon A\cdot j\colon=A\cdot j-c' \tag{8}
$$
where $c'$ is a (formally divergent) constant. Therefore, normal ordering in QED doesn't make the conservation of the current anomalous. On the other hand, in scalar QED a naïve normal ordering does break the Ward identity (cf. this post).
The key point of normal ordering is the following: as in $(5)$, the normal ordered and the non-normal ordered Hamiltonians only differ in a polynomial in $\phi$, of lower degree than the higher interaction term. In other words, the two theories are equivalent, and the only difference is the actual value of the counter-terms. Nevertheless, normal-ordering a Hamiltonian eliminates all diagrams where a propagator closes on itself (aka self-contractions), i.e., it eliminates all tadpole diagrams. Therefore, using a normal-ordered interactions leads to fewer diagrams, and so the perturbative calculation is simpler while keeping the physics unchanged. Measurable quantities are unaffected by the ordering prescription.
In any case, the whole formalism of normal ordering is not completely understood. The standard definition is given only for free fields, and it is far from clear that the definition can consistently be applied to interacting fields as well. See $[3]$ for more details.
Renormalisation
So, how does this all relate to renormalisation?
Renormalisation is a user-defined process: you choose how to do it. Whether you normal-order your Lagrangian or not is independent of how you choose to renormalise your theory. You can go by an on-shell scheme, or use some other prescription to calculate the counter-terms; the scale at which you renormalise is in principle arbitrary; you can chose to renormalise the lowest order vertex functions or some higher correlation function; etc. Any of these choices doesn't care about whether the Lagrangian is normal-ordered or not.
As discussed before, the only effect of normal ordering a theory is that tadpoles diagrams are absent, and this affects the actual value of the counter-terms. But the "algorithm" of renormalisation is unaffected by the ordering prescription (although the fact that the number of diagrams is smaller may simplify the actual process of renormalisation).
Consider for example $\phi^4$ theory, defined by the Lagrangian
$$
\mathcal L=A(\partial\phi)^2+B\phi^2+C\phi^4+D \tag{8}
$$
for some $A,B,C,D\in\mathbb R$.
If you now use $(7)$, we can rewrite the Lagrangian above as
$$
\mathcal L=A(\partial\phi)^2+B'\phi^2+C:\phi^4:+D' \tag{9}
$$
where $B'=B-6c$ and $D'=D+3c^2$.
Now comes renormalisation. In order to calculate $A,B,C,D$ we need to choose some prescription; for example, $D$ (or $D'$) is usually fixed by the requirement that the vacuum has zero energy. This energy is given by the sum of all vacuum bubbles.
In the non-normal ordered theory, the vacuum bubbles are given by
where "$\text{counter-terms}$" are the diagrams with counter-terms,
with value $-iD$ and $-i(A-1)p^2-i(B-1)$ respectively.
If we now insist that $E_0\equiv 0$ to this order in perturbation theory, we get a certain (divergent) value for the coefficients $A,B,D$.
On the other hand, in the normal ordered theory, the vacuum diagrams are
where "$\text{counter-term}$" is given by the same diagrams as before, but with value $-iD'$ and $-i(A-1)p^2-i(B'-1)$ respectively. If we now insist that $E_0\equiv 0$ to this order in perturbation theory, we get a certain (divergent) value for the coefficients $A,B',D'$, different than that of before.
The measurable object, $E_0$, has the same value in both approaches, but the coefficients do not. For example, $D'$ vanishes to first order in perturbation theory, but $D$ does not. Normal ordering has reduced the number of diagrams, and it has caused $D'\neq D$, but it has left the physics unaltered.
The exact same thing happens to higher-order correlation functions. For example, in the non-normal ordered theory, the self-energy of $\phi$ vanishes to first order in perturbation theory; if you consider the normal ordered Lagrangian then $A=B'=0$ to this order, while $B\neq 0$. The difference is caused by the slug diagram (the details are left to the reader; in the normal ordered theory the first non-trivial contribution to $\Pi(p^2)$ is given by the sunset diagram).
, In short,, we can say the following: the diagrams that contribute to a given order in perturbation theory depend on whether or not we choose to normal order the Lagrangian, and this affects the actual value of the counter-terms. But observables are independent of any ordering.
Further reading: Tadpoles, Cephalopods, and 'Complete Normal Ordering', by D. P. Skliros.
References:
