La funzione shuffle di php (
http://php.net/manual/en/function.shuffle.ph) ordina in maniera casuale un array, quindi per "estrarre" dei nomi ti basta creare un array di nome, ordinarlo con shuffle e poi iniziare a ciclare dal primo elemento.
Se la lista iniziale non ha ripetizioni, non le avrà nemmeno quella randomizzata.