Here's a quick way, though I haven't tested every possible scenario:

$string =~ s/ (?=[^{}]*})/_/g;
[download]

Update: Added } to the negated character class to prevent backtracking during the greedy * operation.

I'm still working on the variable substitution...

And here it is (similar to others):

my @sub = qw(men boy girl);
$string =~ s/(?<={)[^}]*(?=})/shift @sub/ge;
[download]