What about https://www.python.org/dev/peps/pep-0393/ ?
I don't fully understand the use case for extracting codepoints from strings, but they could have just added Java-like: codePoints and keep returning code units from old methods. This is CPU and memory efficient and 100% backwards compatible.
I think the problem is the same could have been done in Python 2 (with UTF-8) that would mean less reasons for Python 3.