[Riim]

Получилось через replaceChild:

var TextNode = {
	each: function(callback, parent) {
		for (var childNodes = (parent || document.body).childNodes, i = 0, length = childNodes.length; i < length; i++) {
			var I = childNodes[i];
			I.nodeType == 1
				? arguments.callee(callback, I)
				: I.nodeType == 3 && callback(I, i);
		}
	}
};

window.onload = function() {
	TextNode.each(function(noda) {
		var elem = document.createElement('div');
		elem.innerHTML = noda.nodeValue.replace(/(http\:\/\/www\.youtube\.com\/watch\?v\=[0-9a-z]{11})/gi, '<a href="$1">$1</a>');
		noda.parentNode.replaceChild(elem, noda);
	});
};