Is there a compression format that supports tail operations?

gzip has an --rsyncable option which does essentially the same. The non-standard part would be the gzip-block-aware "ztail" utility, but it seems like you've dealt with that already.