You want a random shuffle. Simply filling the array with random values will very likely produce duplicates. Shuffling multi-dimensional arrays is harder, so the usual advice is to shuffle a one-dimensional array and then copy the results into your final two-dimensional array:

#include <stdio.h>
#include <stdlib.h>
void swap(int *a, int *b)
{
int save = *a;
*a = *b;
*b = save;
}
void random_shuffle(int *a, size_t n)
{
size_t i;
for (i = 0; i < n - 1; i++)
swap(&a[i], &a[i + (rand() % (n - i))]);
}
#define M 4
#define N 4
int main(void)
{
int a[M][N] = {
{0, 1, 2, 3},
{4, 5, 6, 7},
{8, 9, 10, 11},
{12, 13, 14, 15}
};
int i, j;
random_shuffle(&a[0][0], M * N);
for (i = 0; i < M; i++) {
for (j = 0; j < N; j++)
printf("%3d", a[i][j]);
putchar('\n');
}
return 0;
}

For fun: The above code has a very subtle problem! See if you can find it.