Golf you an anagram for great good!
Jelly, 15 bytes

“v0¡µṾ;ḢŒ!QḊX”v


Just to get things started; this is almost certainly beatable. This is basically just a combination of a universal quine constructor and a "pick a random permutation other than the input" function; the latter may be improvable, the former almost certainly is.

Explanation

Universal quine constructor

“v0¡µṾ;Ḣ”v
“       ”v   Evaluate the following, given {itself} as argument:
 v0¡µ          No-op (which starts with "v")
     Ṿ         Escape string
      ;Ḣ       Append first character of {the argument}


This can be seen to be a quine if run by itself. It's also a proper quine by most definitions I know of; it doesn't read its own source (rather, it contains a literal that's "eval"ed, and is given a copy of itself as an argument), it can carry a payload (as seen here!), and the v outside the string literal is encoded by the v inside.

Pick a random anagram

Œ!QḊX
Œ!     All permutations
  Q    Discard duplicates
   Ḋ   Discard the first (i.e. the string itself)
    X  Choose random element


This is really inefficient on a string this long, so I haven't been able to test the program as a whole, but I've tested it on shorter strings and it appears to function correctly.