Sin expresiones regulares te complicas bastante, tendrías que buscar cada ocurrencia de cada par de tags y reemplazar el contenido, puedes hacerlo así, lee los comentarios para entender:
Código PHP:
<?php
//Primero escribe el texto
$texto=$input="Hola mundo del <H>PHP</H>, como <H>estan</H> todos?";
//Luego el texto por el que quieras reemplazar
$repla="REEMPLAZADO!";
//Declara una variable que es donde iremos poniendo el texto
$output="";
//Aqui abres un for iniciado en 0 que actuará como contador para que sepas cuantos reemplazor hay
//Luego buscas si existe el tag <h>
//además compruebas que exista un tag de cerrado </h> y que lo que haya entre ellos sea 0 o mayor
//evitando así que hayan errores como tags mal cerrados o mal ubicados
for($f=0;strripos($texto,"<h>")>-1 and (strripos($texto,"<h>")+3<strripos($texto,"</h>"));$f++){
//guardas solo el final de la cadena donde está la última coincidencia en $output
$output=substr($texto,strripos($texto,"<h>"),3).$repla.substr($texto,strripos($texto,"</h>")).$output;
//Luego haces un nuevo texto, esta vez sin el texto reemplazado
$texto=substr($texto,0,strripos($texto,"<h>"));
}
// Finalmente agregas el último segmento sobrante
$output=$texto.$output;
//Ya puedes imprimir la cantidad de veces que se reemplazo (cantidad de ciclos del for) y la cadena completa con el texto reemplazado
echo "<p>Se ha reemplazado $f veces.</p>";
echo "El nuevo texto es: $output";
?>