My vision of the right way to approach this is to wrap small mutable C++ objects as immutable Python objects - the difference in the behavior of the assignment operator (and augmented assignment operators) makes this much more natural than you might think. You also have to make sure you pass by value or const reference across the C++/Python border, but that's probably already good practice for the (mostly small) objects one would typically want to make hashable and immutable.
That's of course not an answer if we don't want to break all of our low-level APIs by making many more objects immutable. I don't really have a good answer for that, though it may be helpful to do some experiments to see what actually happens if you give a Python set or dict a mutable hashable and then modify it. If the result is "an exception", I'd probably agree with adding hash support to at least some mutable object. If the result is a segfault, infinite loops, or silently incorrect results, I'd be more cautious.