Gracias filemute, no se me habia ocurrido.
Al final he conseguido solucionarlo asi.
Código:
Random rand = new Random();
int x = rand.nextInt(copia.size());
String uno_Nombre = copia.get(x).getNombre();
copia.remove(x);
int y = rand.nextInt(copia.size());
String dos_Nombre = copia.get(y).getNombre();
copia.remove(y);
int z = rand.nextInt(copia.size());
String tres_Nombre = copia.get(z).getNombre();
Lo que hago es coger el nombre del elemento antes de borrarlo, y el get lo hago sobre copia, en cuyo arrayList ya no esta el primer elemento. Asi si en "y" me sale otra vez el 1, ya no cogera el mismo que antes, sino el que se ha desplaza hacia la izquierda.
Gracias de todas formas!