Sure, use Text::Template. You'll need to slightly change the format of your madlib. Instead of something like

the [noun1] [verb2]
[download]

you need to use

the [$noun1] [$verb2]
[download]

But that's not a big change. So you may need to change the script around a bit, but it should work pretty much as is.

use Text::Template;

# read in the story
my @story = <>;

my $hash = { };

# these are the word types that you're
# going to prompt for and include in your madlib;
# the key is what you call the type in the madlib ("adj")
# and the value is what you want to prompt for
my %types = (
    noun => 'noun',
    verb => 'verb',
    adj  => 'adjective'
);

# read in the values from STDIN;
# you may want to change this around.
# 3 means read 3 words of each type (3 nouns, 3 verbs, etc.)
for my $type (keys %types) {
    for my $i (1..3) {
        print "give me a $types{$type}: ";
        chomp($hash->{$type . $i} = <STDIN>);
    }
}

# set up a new template object:
# get template from array @story where template
# variables are in [] (DELIMITERS)
my $t = new Text::Template(TYPE => 'ARRAY', SOURCE => [ @story ],
    DELIMITERS => ['[', ']']);

# fill in the template with the values you read into $hash;
# so in the template, [$noun1] => $hash->{'noun1'}
my $story = $t->fill_in(HASH => $hash);

# then just print it out
print $story;
[download]