Traverse a matrix using a linear index to get an evenly distributed values sample

I'm looking for an algorithm idea on how to traverse a matrix using a linear index while avoiding row/column based traversals to get a more diverse distribution of values.

To understand this better, think of an image that's split in blocks, with N rows & M columns. I need to process each image block sequentially (from 1 to NxM) but I don't know in advance what the processing time will be for each block ( blocks that are close together tend to have a similar processing time, with small variations).

During processing, I need to be able to estimate as best as possible the remaining processing time based on the number of blocks that have already been processed & their associated processing time. For this reason, traversing the blocks by columns or by rows will not give an accurate estimation so I need to find another way of traversing the matrix that would pick values from different zones of the image.

It's also important to be able to determine the blocks processing order based on a linear index (from 1 to NxM), without calculating them in advance. The algorithm that returns the row & column corresponding to the linear index should be as fast as possible.

Shorter version of the question

For a liner index named idx, I need to get a corresponding row & column pair from a matrix with N rows & M columns while avoiding a row/column based traversal.

For each idx between 1 and NxM, the algorithm would return a [row, column] pair so that all the rows & columns combinations are returned exactly once.

Example

(the values in the matrix represent the linear index's value that's associated with that row&column position)

 1 17 13  9  5
 6  2 18 14 10
11  7  3 19 15
16 12  8  4 20

The above example is for a diagonal traversal that would produce a better distribution of values that a row/column based traversal.

Another possible solution would be to split the matrix into smaller blocks & traverse those blocks in rows/columns. For example a 4x5 matrix could be virtually split into 2x2 blocks and those smaller blocks could be traversed by rows or columns (e.g. idx(1) = block1[1, 1], idx(2) = block2[1, 1], etc.). The traversal would look something like this:

 1 13 |  3 15 |  5
 7 17 |  9 18 | 11
------+-------+---
 2 14 |  4 16 |  6
 8 19 | 10 20 | 12

Any other traversal ideas are welcomed.

Ideally, this algorithm would translate to a math formula to calculate the row & column based on the linear index, possibly with a few conditions (IF statements) to compensate for missing values, etc.