Java - Duda Java (matrices)

Hola. Tengo una duda que supongo que será una chorrada pero no sé cómo hacerlo ya que soy nuevo en esto de la programación.
Tengo una matriz de 4x4 y quiero desordenarla. ¿Cómo lo haríais?
Se me había ocurrido crear otra matriz 4x4 que fuera cogiendo aleatoriamente los datos de la 1ª, pero no sé cómo hacer para marcar que no se repitan las posiciones ya cogidas.
El código es:

matriz2 = new char[4][4];
for (int i=0; i<4; i++){
for (int j=0; j<4; j++){
matriz2[i][j] = matriz[(int)(Math.random()*4)][(int)(Math.random()*4)];
}
}

Gracias por adelantado.

Lo que podrias hacer es iniciar la matriz nueva con X valor que nunca existira entre los datos que almacenaras, por ejemplo -1.009

Antes de guardar un nuevo valor, revisas si es igual a -1.009, si es verdadero, guardas el nuevo valor, de lo contrario a seguir buscando hasta que acompletes la matriz.

buen día.