Unless I'm misunderstanding what you want, Archive::Zip should do what you ask. The following snippet will add the file s2.tst to the zip file tst.zip, creating tst2/ if it doesn't already exist in the archive.
#!/usr/bin/perl
use warnings;
use strict;
use Archive::Zip qw( :ERROR_CODES );
my $zip = Archive::Zip->new();
$zip->read('tst.zip') == AZ_OK or die "read error\n";
$zip->addFile('tst2/s2.tst');
$zip->overwrite() == AZ_OK or die "write error\n";
According to the docs, Archive::Zip can also rename already-existing items in a Zip file.
Update: Looking at your question again, it seems I may have misunderstood it. :) From the doc's, it seems like Archive::Zip should still be able to do what you want, using the replaceMember() method, but my initial tests don't seem to be working. I'll play with it some more.
Update2: Ah, got it. I think this is what you want:
#!/usr/bin/perl
use warnings;
use strict;
use Archive::Zip qw( :ERROR_CODES );
my $zip = Archive::Zip->new();
$zip->read('tst.zip') == AZ_OK or die "read error\n";
my $m1 = $zip->memberNamed('tst2/s2.tst');
$m1->fileName('foo/tst2/s2.tst'); # Rename the file, adding
+a subdir
$zip->overwrite() == AZ_OK or die "Write error\n";
bbfu
Black flowers blossum
Fearless on my breath |