I find the fundamental approach here a bit worrying. Frozen and non-frozen objects should be distinct types. The following code should not be able to fail for any reason except out-of-memory IMO:
if isinstance(l, list):
l.append(1)
Changing this invariant is such a fundamental change in the mental model programmers need to have that it IMO requires equally fundamental justifications, if it can ever happen. I have not seen any such justifications yet. In rust, every variable has tracked mutability states - this is not what is being added in this PEP, what is being added is every object having a tracked mutability state.