I'm not sure if you can add files to bzip2 archives without first extracting. However here is one solution that just came to my mind (giving you the pseudoish algorithm):
1. For each [file] in [all small files]
1.1 compress [file] into [file].bz2
1.2 (optionally verify the process in some way)
1.3 delete [file]
2. For each [bzfile] in [all bzip files from step 1]
2.1 append to tar (tar rvf compressedfiles.tar [bzfile]
2.2 (optionally verify the process in some way)
2.3 delete [bzfile]
Now you should have a tar file containing all files individually bzip2:ed files. The question is how much overhead bzip2 adds to the individual files. This needs to be tested.