Con document.write no podés hacer eso porque sobreescribís el documento. Pero tampoco lo usás bien ya que cuando asignás un setInterval a una variable, la variable asume el valor de un identificador numérico único que javascript crea para referenciar a ese setInterval (generalmente usado para hacer un clearInterval). Probá así:
Código PHP:
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Documento sin título</title>
<script>
function frases_alea(){
frases = new Array();
frases[0] = "<a href='http://www.eurolloyd.es/seguros/seguros-de-coche/calcula-el-precio.html' onclick='openBack(this.href);return false;'>Consulta y beneficiate de nuestras nuevas tarifas para el seguro de tu coche</a>";
frases[1] = "En Eurolloyd aplicamos los descuentos de tu seguro actual en nuestros precios";
frases[2] = "Si quieres seguridad para tí y los tuyos, <a href='http://www.eurolloyd.es/seguros/seguros-de-accidentes/precios-y-coberturas.html' onclick='openBack(this.href);return false;'>consulta nuestro seguro de accidentes para el motorista.</a>";
frases[3] = "Si te interesa nuestro precio, contrata tu seguro directamente desde nuestra p·gina web";
aleatorio=Math.floor(Math.random()*4);
return frases[aleatorio];
}
onload=function(){
document.getElementById('algo').innerHTML=frases_alea();
setInterval(function(){document.getElementById('algo').innerHTML=frases_alea();},5000)
}
</script>
</head>
<body>
<div id="algo"></div>
</body>
</html>