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.

CJam, 17 bytes

{`"_~"+m!(a-mR}_~

This isn't going to finish any time soon, so no TIO link this time.

As a consolation, here is a 20 byte solution that does terminate very quickly:

{`"_~"+:S{mr_S=}h}_~

Try it online!

Explanation

{`"_~"+   e# Standard quine framework, leaves a string equal to the source
          e# code on the stack.
  m!      e# Get all permutations. The first one will always be the original order.
  (a      e# Remove that copy of the source code and wrap it in a new list.
  -       e# Remove all copies of the source code from the list of permutations.
  mR      e# Pick a random permutation.
}_~

The 20 byte solution instead shuffles the source code until its different from the original.

Python 2, 117 bytes

Surprisingly this solution is shorter than I expected. Shuffles source code, until it differs from the original.

-2 bytes, thanks to @mbomb007
-3 bytes, thanks to @Wondercricket

Try it online

s=r"""from random import*;R='s=r\"""'+s+'\"""'+';exec s';L=R
while L==R:L=''.join(sample(R,len(R)))
print L""";exec s

This is one of the basic quines in python, that I've modified

s = r"print 's = r\"' + s + '\"' + '\nexec(s)'"
exec(s)

Generating anagram is done by random module

L=R
while L==R:L=''.join(sample(L,len(L)))

Where R contains sourcecode

s=...
R='s=r\"""'+s+'\"""'+'\nexec s'

Triple quotes were needed as I was forced to keep actual lineseparators in code. Anagrams will have 3 lines anyway.