1) Note my idea that creating "bzipped tarballs with identical checksums is rather hard" turned out to be entirely incorrect.
2) I was able to create identical bzipped tarballs of linux-2.6.39 and linux-3.0. I also was able to create identical bzip2 versions of a few recent -rc and -stable patches. So it seems the tar an bzip2 formats are more likely to generate reproducible results than I expected. Ditto for the git commands I used to generate their input.
(3) Boring details: for linux-2.6.39 I only needed to add "-c tar.umask=0022" to "git archive" to create an identical tarfile. For the -rc patches I needed to edit one git diff index line (ie, an "index <hash>..<hash> <mode>" line) because one hash abbreviation changed due to, in short, recent additions to the repository. Trivial changes, really. Other files I could easily recreate with rather obvious command lines, like "git diff v3.0..v3.0.4 | bzip2 -9".)