Matrices

[Nendrel]

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&lt4; i++){
for (int j=0; j&lt4; j++){
matriz2[i][j] = matriz[(int)(Math.random()*4)][(int)(Math.random()*4)];
}
}

Gracias por adelantado.