Equivalent Colorings of Graphs
Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices.  So, here is one plausible algorithm you could use:

We are given an existing coloring $C$.  Pick two vertices $v,w$ randomly.  We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph.  If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use).  If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick).  Then extend this to a coloring for the new graph.

If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one.  Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure.  In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$.  Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.

So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once.  On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.