You can easily add new files at the end, then rewrite the central directory header (which is at the end of the file for exactly this kind of reason: not have to rewrite everything to add new files). And because the CDH specifies offsets to files, you can replace the old entry and put the new one there (replace old offset by new offset, done). This does however mean the old entry will still be in the file until you "garbage collect". That's if the new version of the file is bigger than the old one of course, if it's smaller or the same size you can just overwrite the old entry and not touch anything.

One could even imagine padding files in the archive so there's some leeway in growing the compressed files, it'd likely depend on the format expression.