If you have an external tar executable, I would use that to create the tar file and append the files to the archive. There seems to be Archive::Tar::Wrapper, which should make switching from Archive::Tar trivial.
There also is Archive::Tar::Stream, which has a different API but should be able to just append files with the ->AddFile() call.