I think the convert to str -> process as str -> convert back to bytes approach is a good one - it's the same one we use in urllib.parse.

In this case, since we explicit need to handle mixed encodings, I also agree with the idea of using surrogate escape to make it possible to tunnel arbitrary bytes through the process, and expose that as a new module level API for Python 3.5.