a ver, xml es un simple archivo de texto plano, en donde se guarda información auto-definida...
En XML por si solo no puede colocar una cabecera, en tu caso 1 el PHP que edita la info del XML está mal programado y hay que colocarle en ese PHP que guarde el XML con el encoding que desees...
Ahora bien, siguiendo la idea anterior, en XML no puedes hacer random ni nada, ya que es un texto que no se ejecuta...tienes que hacerlo desde algún lenguaje de programación como PHP que toma la info del XML y la le haga random y lo que quieras, talvés mostrar por pantalla un nuevo XML con el random realizado...
Tus problemas no son de XML, son de PHP
Saludos