[Gekt0r]

Либо innerHTML родительского для всех картинок блока и replace'ом по RegExp'у.

так можно, но уж слишком геморно получается в итоге, работать со строками, много всего надо учитывать.. Я хотел через DOM, так проще и эффективнее, но не совсем понимал, как это сделать

var parent = img.parentNode;
parent.removeChild(img);
var elem = document.createElement("a");
elem.href="http//www.mail.ru";
elem.appendChild(img);
parent.appendChild(elem);

Вот это именно то, что надо, спасибо огромное!