Options:
1) Use UTF-32 everywhere. When space is an issue, just compress it - especially on disk. If you need random access to a string, use a seekable compression algorithm on it on-the-fly. Alternatively, use a compression algorithm with checkpoints and maintain a sorted list of where checkpoints start and how far along in the associated decompressed text you are. (Effectively rolling your own.) Note that this method doesn't work well with writes.
2) Use an interesting variant of a rope. Use a rope, but a) keep track of "logical characters" instead of code points - what unicode calls graphimes, IIRC, and b) have each node have an encoding - and restrict that all characters within a specific node have the same width. This allows for pretty much everything being sublinear. If you allow a bit in a node for "special" nodes (i.e. reversed, lazy-loaded, slice of another node, that sort of thing), reversing, among other things, is actually truly O(1). Bunches of optimizations here - you want to fall back to a "node" that's a flat array for small strings, you want to potentially use overlong encodings internally where appropriate (i.e. if you have 1 1-byte character in a bunch of 2-byte characters, that sort of thing), you want to have some encodings that aren't fixed-width (for things like reading a bunch of bytes from a file), you want to have an encoding that's "unknown" / binary data.
Thoughts:
1) Why on earth does any higher-level language still use byte or codepoint counts for length? And why don't lower-level languages at least have a way to count / index by graphimes?
2) I do not like UTF-8 / 16. It's effectively bad huffman encoding. It's an attempt to save space, but it doesn't even do that well. About the only advantage of UTF-8 is that ASCII maps to it reasonably well. And it has a bunch of disadvantages, chief among them being that if you write a single miltibyte character, you potentially have to rewrite the entire string.