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";
[download]

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";
[download]

bbfu
Black flowers blossum
Fearless on my breath