Estube probando de todas las maneras con la función shuffle(), pero no habia manera. Por fin he conseguido hacerlo, lo posteo por si ha alguien le ocurriera lo mismo.
Código PHP:
$array[1] = "Valor1";
$array[2] = "Valor2";
$random = rand(1,count($array));
echo $array[$random];