Looking for an algorithm to iterate over essentially different solutions
All solutions are equivalent modulo the equivalence you have given.

Suppose $(a_{i,j})_{1\le i\le 4,1\le j\le 6}$ is some solution. Each row misses two labels, and these pairs of labels form a partition of $\{1,\dots,8\}$ (otherwise some label would occur too often). But then we can choose an exchange of labels modulo which row $1$ misses $7,8$; row $2$ misses $5,6$; row $3$ misses $3,4$; and row $4$ misses $1,2$.

Each row can then be reordered to arrive at the solution

$A=\begin{pmatrix}1&amp;2&amp;3&amp;4&amp;5&amp;6\\1&amp;2&amp;3&amp;4&amp;7&amp;8\\1&amp;2&amp;5&amp;6&amp;7&amp;8\\3&amp;4&amp;5&amp;6&amp;7&amp;8\end{pmatrix}$

Since every solution is equivalent to $A$, by transitivity, they are all equivalent.