Я знаю, что innerHTML якобы злой, но я думаю, что это самый простой способ изменить текст ссылки. Например:
<a id="mylink" href="">click me</a>
В JS вы можете изменить текст:
document.getElementById("mylink").innerHTML = new_text;
И в Prototype/jQuery:
$("mylink").innerHTML = new_text;
работает отлично. В противном случае сначала необходимо заменить все дочерние узлы, а затем добавить текст node. Зачем беспокоиться?