Solución:
La forma recomendada es a través de la manipulación DOM, pero puede ser bastante detallada. Por ejemplo:
// <p>Hello, <b>World</b>!</p>
var para = document.createElement('p');
para.appendChild(document.createTextNode('Hello, '));
// <b>
var b = document.createElement('b');
b.appendChild(document.createTextNode('World');
para.appendChild(b);
para.appendChild(document.createTextNode('!'));
// Do something with the para element, add it to the document, etc.
EDITAR
En respuesta a su edición, para reemplazar el contenido actual, simplemente elimine el contenido existente, luego use el código anterior para completar el contenido nuevo. Por ejemplo:
var someDiv = document.getElementById('someID');
var children = someDiv.childNodes;
for(var i = 0; i < children.length; i++)
someDiv.removeChild(children[i]);
Pero como alguien más dijo, recomendaría usar algo como jQuery en su lugar, ya que no todos los navegadores son totalmente compatibles con DOM, y aquellos que sí tienen peculiaridades que se tratan internamente mediante bibliotecas de JavaScript. Por ejemplo, jQuery se parece a esto:
$('#someID').html("<p>Hello, <b>World</b>!</p>");
La mejor forma de hacerlo es usar document.createTextNode. Una de las principales razones para utilizar esta función en lugar de innerHTML es que todo el escape de caracteres HTML se encargará por usted, mientras que usted mismo tendría que escapar de su cadena si simplemente estuviera configurando innerHTML.
Puede obtener el mismo efecto manipulando el DOM. La forma más segura de cambiar el texto es eliminar todos los nodos secundarios del elemento y reemplazarlos con un nuevo nodo de texto.
var node = document.getElementById("one");
while( node.firstChild )
node.removeChild( node.firstChild );
node.appendChild( document.createTextNode("Two") );
La eliminación de los nodos secundarios elimina el contenido de texto de su elemento antes de reemplazarlo con el nuevo texto.
La razón por la que la mayoría de los desarrolladores evitan el uso de innerHTML es que el acceso a elementos a través del DOM cumple con los estándares.