> And frankly, if you don't roll it yourself, what are you going to use other than ICU?

GNU libunistring: http://www.gnu.org/software/libunistring/