Gray-like code with maximum value <= maximum value of original symbol
Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two.  I'll describe how, below.

I will say that $a_0,\dots,a_{n-1}$ is a Gray code sequence for $0,1,\dots,n-1$ if each $a_i$ is in the range $0..n-1$, and if each $a_i$ differs from $a_{i-1}$ in a single bit position.  Note that this generalizes the usual notion of a Gray code, to the situation where the numbers are not a power of two.

Let $n = 2^t + u$, where $u \le 2^t$.  We'll use two steps:


First, recursively construct a Gray code sequence for the numbers $0..u-1$.  Suppose the sequence is $x_0,x_1,\dots,x_{u-1}$.  This means that each $x_i$ is in the range $0 \le x_i \le u-1$ (for each $i=0,1,\dots,u-1$), and each $x_i$ differs from $x_{i-1}$ in a single bit position (for $i=1,2,\dots,u-1$).  This in turn gives us a Gray code sequence for the numbers $2^t,2^t+1,2^t+2,\dots,2^t+u-1$ by just adding $2^t$ to each element in the sequence: specifically, $2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1}$.
Second, construct a Gray code sequence for the numbers $0..2^t-1$ that starts at the number $x_{u-1}$.  A cool fact about the standard Gray code construction (for a power of two) is that it is cyclic, i.e., you can start anywhere and get to all the numbers, from that starting point.  Let $y_0,y_1,\dots,y_{2^t-1}$ be this sequence.  As mentioned, we have $y_0 = x_{u-1}$.


Now if we just concatenate these two sequences, we get an ordering of $0..n-1$ where each number in the sequence differs from its previous number by a single bit.  In particular, the full sequence is

$$2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1},y_0,y_1,\dots,y_{2^t-1},$$

with the $x$'s and $y$'s defined as above.  This gives a simple and easy to implement construction for what you want.



Caution: Iterating through elements of the matrix in Gray code order will trash your cache.  Caches are optimized for sequential access.  You're doing random access (jumping around in the address space), so the caches will be useless and every memory access will be a miss in the cache.  As a result, performance might suffer.  Beware.