Guarda los posibles números en una lista (un LinkedList, por ejemplo) al principio del programa. Cuando quieras rellenar la matriz, genera con random entre 0 y el número de elementos de la lista uno de los índices, retira el elemento de la lista y mételo en la matriz. Repite el proceso en un bucle, teniendo en cuenta que la lista tendrá cada vez un elemento menos.
El pseudocódigo puede ser así
Código java:
Ver originalRellena un lista los posibles valores
para cada elemento de la matriz
genera un indice aleatorio entre 0 y elementos lista - 1
retira de lista ese elemento y mételo en la matriz.
Se bueno.