Prova a guardare la bufferizzazione ob_start e consorti. In altre parole. Tutti gli echo o print vanno in un buffer. Poi puoi salvare il contenuto del buffer in una variabile. Fai lo str_replace nella variabile e poi la stampi a video.