There was no way to gradually improve Unicode support in Python without breaking things, because a big part of it was stuff like implicit str/unicode conversions - that were broken because they practically never use the right encoding, but that you can't remove without introducing as much breakage as Python 3 did.
You lack imagination here :) There are several solutions that could have been pursued, including introducing a completely new type and effectively duplicating the existing string library for it.
It's not just the string library that is affected. It's literally every API in the stdlib that returns a string. You'd have to fork all of those, because changing any of them to return a completely new type would be a breaking change as well.
