I've filed issue 24991 to suggest reviewing the wider question of how we deal with identifying whether or not a type's instances are expected to be "truly immutable" in the Python 3.6 time frame.

For 3.5, I think Nathaniel's proposed patch restoring the assumption that non-heap types are immutable by default, and whitelisting __class__ assignment for PyModuleType specifically is a good way to resolve this with minimal code churn late in the release cycle.