One way I've done this is to use Archive::Tar's add_data method. I read the file into a scalar which becomes add_data's second argument. I then use stat to populate a hash for the third argument. The first argument becomes the name I want to file to take on.

One thing I haven't tried that may work for you: If you want relative path names (no leading slash in your example then) have you tried using chdir to first change to the relative leading directory, then adding relative file names?