Te lo explico , porque lo que pides es lógica. El código hazlo tú
1. Creas otro arraylist.
2. Haces un bucle que se ejecute mientras en el arraylist que tienes (el original) haya contenido (hay métodos que te dicen si una arraylist está vacía)
3. Si no está vacía haces un random entre 0 y el tamaño del arraylist original.
4. Coges el contenido de index el número que te salió en el random.
5. Le haces .add a la arraylist que creamos en el punto 1 de contenido que sacamos en el punto 4.
6. Borramos del array original el contenido de dicho index.
Ya está
Un saludo!