str_replace ile olacak iş değil gibi bu çünkü linklerin hiçbirinde "dofollow" ibaresi yer aldığını sanmıyorum. İşiniz DOMDocument kullanılarak çok daha hızlı ve temiz bir yolla yapılabilir

Size küçük bir fonksiyon hazırladım;
$html = '<a href="http://test.com" rel="nofollow">asd</a>
<a href="http://test.com" rel="dofollow">atd</a>
<a href="http://test.com">asd</a>';

function addRel($html){

$doc = new DOMDocument();
$doc -> loadHTML($html);
$links = $doc->getElementsByTagName('a');

foreach($links as $link) {
$link->setAttribute('rel', 'nofollow');
}

$out = simplexml_import_dom($doc)->asXML();
return $out;

}

echo addRel($html);

/* Çıkan:
<html><body><a href="http://test.com" rel="nofollow">asd</a>
<a href="http://test.com" rel="nofollow">atd</a>
<a href="http://test.com" rel="nofollow">asd</a></body></html>
*/
Sayfayı yüklemeden HTML'i bu fonksiyondan geçirip yüklerseniz tüm linkler nofollow almış olarak çıkaracaktır Elimden geldiğince (PHP bilgim yettiğince) yardımcı olmaya çalıştım.