noreferrer.user.js

// ==UserScript==
// @name           noreferrer
// @namespace      http://ss-o.net/
// @include        http://*
// ==/UserScript==

document.body.addEventListener('DOMNodeInserted',noref,false);
noref({target:document.body});

function noref(e){
	if (e.target.getElementsByTagName) {
		var as = document.evaluate('descendant-or-self::a', e.target, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
		for (var i = 0, l = as.snapshotLength;i < l;++i){
			var a = as.snapshotItem(i);
			if (
			    a.href.indexOf('http') === 0 &&
			    a.host !== location.host &&
			    !/noreferrer/i.test(a.rel)
			   ) {
				a.rel = (a.rel ? a.rel + ' ' : '') + 'noreferrer';
			}
		}
	}
}

DOMNodeInserted とか、 f({target:document.body}) とか、 a.href.indexOf('http') === 0 とか。
string.indexOf ってあるんだなあ。正規表現でやる方法しか思いつかないや