I've tried the standard gnu releases 1.2.4, and 1.3.9, on FreeBSD. Perhaps Linux distros have integrated it...How old is the gzip release you're using; what specific version do you have?
I confirm that on at least gzip v1.3.3, dated 2002-03-08, the option "--rsyncable" to "make rsync-friendly archives" is included.