I worry about how the payload chooser will enumerate and load the other payloads.
Enumerate? It can just ask LAR what files are there. Put all payloads in some subdir or whatever, low-tech is good ;-P
As far as the name / notes issue is concerned, I'm not clear on how we can keep the headers uncompressed
You can keep the headers uncompressed by, well, keeping the headers uncompressed! This has nothing to do with the binary format used, but everything to do with how you use your compressors.
Why do you need the headers uncompressed, anyway? Any sane compression library allows you to ask "give me the first nnn bytes".
and be able to access individual segments in the ELF without eventually having to uncompress the whole thing.
Why do you want to load individual segments? When would this be useful?
I am also concerned about the extra step when we decompress to memory and then copy into place. How can we get around these issues and still call the result a true ELF file?
Again, that is more a feature of your compression than a feature of the binary format.
Why is an extra copying step harmful, btw? Not because of the few milliseconds that copying costs, even on the lowest-end hardware.
Segher