Perhaps you can use s///g in scalar context, keeping track of where you are with pos(). You can document all the offset differences so that you know there's a three byte warp here, and a two byte hole there, or whatever.
How exactly do you apply the regex substitutions?

-nuffin
zz zZ Z Z #!perl