It is nice that you were able to make it work with ordinary gzip files. In bioinformatics, an approach to this problem has been to create a gzip-backwards-compatible (i.e., can be read by zcat but not written to by gzip) format called BGZF [1] which acts like ordinary gzip except each compressed block is the same size, which eases indexing and partial decompression.
I would be interested to know how you solved the problem of finding the right block and offset when each compressed block can be an arbitrary size as it is in ordinary gzip format.
[1] http://blastedbio.blogspot.com/2011/11/bgzf-blocked-bigger-b...