Have a look on Mail::Internet and/or Mail::Box. Basicallly, you'll first decompose/split the big all-encompassing string you have into an array of lines. Then you can easily fiddle with the header lines you wish to mangle and send it out afterwards.