Hola kiewic:
Cuando hablas de aleatoriedad debes pensar en javascript...
var fondos = ["fondo1.gif", "fondo2.gif", "fondo3.gif"];
function fondoAleatorio() {
var elFondo = fondos[Math.floor(Math.random() * fondos.length)];
document.body.style.backgroundImage = "url(" + elFondo + ")";
}
...
<body onload="fondoAleatorio" >
Saludos
