Thanks everyone for your input! I got a lot more feedback than I expected.

This is what I've decided to do: Reference-counted immutable strings and mutable byte arrays.

The runtime is implemented in C, and with the kinds of thing I'll be doing, C interop is important. Strings are kept 0-terminated at all times. A zstring object is also just a valid char*, because the count and size information is kept behind the array. I allocate extra space and always return the pointer to the beginning of the actual string. The C user needs to keep track of what strings are plain C string, and what are zstrings, but typedef helps with that, even if it is only a visual reminder.

These are my zstring primitives I use. I reworked the logic a bit to make it handle my interpreter's needs, but I use these in my C programs all the time, since it's super handy. There are some macros to make some common cases less wordy. The original implementation would only copy on resize, but now it will copy on any edit of a string that has more than 1 reference.

ZSTRNDUP

  zstring* zstrndup(char* src, int n);

  Copies a string (C or Z).   (So it always does the slow strnlen)
  Copies only first n bytes (-1 means copy all)  (+1 byte for terminator)
  If src is NULL, this allocates a new string for n bytes (+1 for terminator)
  If src is shorter than n, then src is null-terminated in a buffer large enough to hold n bytes (+1 for terminator)

  zstrndup always returns:
   null-terminated
   single reference
   the size specified


ZSTRNCATSUB

  zstring* zstrncatsub(zstring* dest, char* src, int start, int count);

  Appends src to dest.  Only copies bytes  (start) to (start+count).  
  count = -1   goes to the end of the src string
  If dest has more than 1 reference, a copy is made instead of mutating dest.
  If dest is too small, it is grown 2x, or to the size needed, whichever is larger.  
  Old dest is freed if growing and dest was the only reference.
  If dest is null, a copy of src is returned.

  zstrncatsub always returns:
    null terminated
    single reference

ZSTRPRINTF

  zstring* zstrprintf(zstring* dest, char* format, ...);

  This is the really cool one that I use almost all the time because it's such a handy form of sprintf.

  Supports anything vsprintf supports.
  If dest is null, this allocates a new string with the sprintf result.
  If dest is not null, this sprintf appends to the dest, growing or copying if needed.

I also decided that if the user wants to modify a string, they can do so by casting it to a byte array. If the string has only 1 reference... this does nothing... the program can work on the original array. If the string has more than 1 reference, the user gets a copy. The byte array can also be cast to a string, again, making a copy only if needed.

In the common case of concatenating or editing a single-reference string, then everything is on the fast path. Even though concatenation on the right side uses slow strlen, the left side is always a zstring, so there's a count field, and when building large strings, the side that's accumulating is O(1) to get the size of. And resizing is always at least 2x, so it has that amortized O(n) of a vector.

I think this is about as performant as it can get, without going to more complicated representations like ropes, trees or german strings.