I know this is late, not sure what the OP ended up going with, but here are some suggestions:
You could create a new partition using a filesystem of your choice and copy everything you want to store to that partition. Then shrink the partition as small as you can to save space. Then you can use e.g.
dd to create an image of the partition, say it's
/dev/sdc3, at its simplest:
dd if=/dev/sdc3 of=backup_image.bin
For Windows Google for "dd for windows" or find an equivalent program that can make a byte-for-byte image of a partition or device.
Then, that image file can be placed in long term storage. As long as you have access to the file and your long term storage media supports random seek, you can just mount the file directly, e.g.:
sudo mkdir /media/backup
sudo mount /path/to/backup_image.bin /media/backup
For Windows, Google for "windows mount partition image".
You'll have full access to the data and only the minimum amount of reads necessary to support navigation through the filesystem and access to that file will be performed.
Another, more obvious option, is to simply not combine your files into a single archive file. Create a normal filesystem on your long term storage and just copy the files to it. Filesystems already provide the means to access specific files without accessing unneeded data, you may not have to reinvent a wheel.
Also there are proprietary formats like the one you describe, for example, backup software like Acronis can back up data to network mounted drives or wherever, into ".TIB" files that can be browsed (and data extracted) without requiring a read of the entire file. I don't know if Acronis supports browsing of Linux/OSX filesystem backups but I do know it supports this type of browsing for FAT32 and NTFS backups. I'm sure there are others.