Encoding strings internally as UTF-8 is a fine idea, usually you don't need constant-time access to individual code points. E.g. PyPy (faster Python, with JIT) does so. Many other languages also save strings as UTF-8.

And then you have to either re-train them to use string cursors or you have lots of people writing inefficient string code.

Not really, no. PyPy demonstrates that.

Sure it does. Where CPython does byte inflation to make sure random access works, PyPy makes you use an extra indexing structure for cases where you can't just advance one char at a time.

I must say it is a rather elegant way, but it still fits firmly within "a new way or inefficient code".