Sampling without replacement along a 2D grid in Cython without gil (can be in C++)

Question

I have essentially a 2D grid of N by M (i.e. N rows, and M columns). I would like to sample from this grid without replacement in Cython without requiring the GIL. I would want something like this

for j in range(n_samples):
   row_idx, col_idx = sample_without_replacement(grid)

So for example, say my 2D grid is 3 x 4, then I might get the following samples

(0, 3),
(0, 2),
(2, 1),
(3, 0)

Is there a simple way to do this in Cython?