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.