<p id="nombre">Mi nombre es Pedro</p>
var nombre = document.querySelector("#nombre").innerHTML;
nombre = "Mi nombre es Álvaro";
esa era la solución de Alvaro, como podemos ver está usando la propiedad innerHTMl luego de seleccionar el elemento a cambiar, los cual está mal ya que lo tendria que hacer en su variable, de esta forma:
<p id="nombre">Mi nombre es Pedro</p>
var nombre = document.querySelector("#nombre");
nombre.innerHTML = "Mi nombre es Álvaro";