If you try to set the __class__ of a type which doesn't support "__class__" assignments, you get the error message:

    TypeError: __class__ assignment only supported for heap types or ModuleType subclasses

However, the actual restriction doesn't require a subclass of "ModuleType"; the below code works:

    import random
    class M(type(random)):pass
    random.__class__ = M

Thus the error message is incorrect.

Your example works because random is a module:

py> from types import ModuleType
py> import random
py> type(random) is ModuleType
True

Since random is an instance of ModuleType, your class M is a subclass of ModuleType, and assigning to random.__class__ is allowed.

I'm closing this issue, but if can demonstrate an actual problem, please feel free to re-open it.