You could start the encoding with two bytes, so that if the most significant bit of the first byte is 0, the length is that byte plus another. That gives you 32KiB strings with just a byte more. Short strings might suffer, but I think the overhead is reasonable.

The next level (110x xxxx) would give you 8MiB strings, which are going to be fine for most things.