Somewhat different approach:

#!/usr/bin/perl -w
use strict;

my $line='boy boy girl boy girl boy girl girl';
my ($pos, @pos);
my $last = 0;
{
    $pos = index $line, 'boy', $last;
    last if $pos == -1;
    push @pos, $pos;
    $last = $pos + 1;
    redo;
}
substr $line, $pos[rand(@pos)], 3, 'man';
print "$line\n";
[download]

Update: Same idea but using 'pos()':

#!/usr/bin/perl -wl
use strict;

my @pos;
$_ = 'boy boy girl boy girl boy girl girl';
push @pos, pos() - 3 while /boy/g;
substr $_, $pos[rand @pos], 3, 'man';
print;
[download]