I asked a colleague and she came up with a different proof:
So if you have a normal subobject, it is the kernel of its cokernel. And you have another regular epi. If you take the pushout of these two regular epis, you get what is called a regular pushout, a pushout square where all morphisms are regular epis. In certain contexts (e.g. semiabelian) this is then automatically a double extension (the thing I told you about: the comparison morphism to the pullback is also a regular epi). So if you take kernels "upwards", the comparison between the kernels is also a regular epi. This means that you do get an image factorisation of the composite of your original normal subobject and regular epi through that second kernel you've taken.
If I understand correctly, the diagram to keep in mind is the one shown below:

Here, $A \to B$ is the regular epimorphism we start with, $M \to A$ is a normal monomorphism, $A \to C$ is the cokernel of $M \to A$, $D$ is the pushout of $A \to B$ and $A \to C$, $E$ is the pullback of $B \to D$ and $C \to D$, $N \to B$ is the kernel of $B \to D$, and $P \to E$ is the kernel of $E \to C$.