Certo che si può fare
La strada migliore è quella che suggerisce razorblade...
Quindi io modificherei l'ultimo tuo esempio così:

Codice PHP:
$n = rand(1,20);

$title = array();
$title[1] = "frase 1 ";
$title[2] = "frase 2";
$title[3] = "etc";
$title[20] = "frase 20";

<title><?php echo $title[$n]; ?></title>