Here is an implementation I came up with (only generate, as generate_tree is the same idea):

use warnings;
use strict;

my %dict = 
(
  sentence     => [[qw/ noun_phrase verb_phrase /]],
  noun_phrase  => [[qw/ Article Noun /]],
  verb_phrase  => [[qw/ Verb noun_phrase /]],
  Article      => [qw/ the a /],
  Noun         => [qw/ man ball woman table/],
  Verb         => [qw/ hit took saw liked /]
);


sub rand_elt
{
    return $_[rand scalar @_];
}


sub listp
{
    return ref($_[0]) eq "ARRAY";
}


sub generate
{
    my $phrase = shift;
    
    if (listp $phrase)
    {
        return [map {@{generate($_)}} @{$phrase}];
    }
    elsif (exists $dict{$phrase})
    {
        return generate(rand_elt(@{$dict{$phrase}}));
    }
    else
    {
        return [$phrase];
    }
}

print join(' ', @{generate("sentence")}), "\n";
[download]

Overall I'm satisfied with the result - it's an elegant functional code that represents the solution in an intuitive recursive way, without too much overhead.

Some observations:

1. Note that Lisp also doesn't have the random-elt function built-in, it's defined by Norvig elsewhere.
2. In the attempt to "transliterate" the Lisp code, Perl succeeds nicely. Interestingly, the elegant mappend construct that's defined in the Lisp/Python versions is implemented trivially with Perl's native map.
3. Perl also allows to avoid defining the rewrites the Lisp version defines, since it has easier hash access.
4. In Lisp, all objects are pointers and the data they point to has a type. Thus, you can ask (listp foo). In Perl it doesn't work - arrays/lists and scalars are very different. Hence, in my implementation a "list" is an array ref, it allows to define $phrase as a scalar. The listp function I defined helps spot the difference. In general, Lisp's handling of lists is much cleaner, since Perl requires @{$..} sugar.

Generally, this code is "the Lisp way", or rather "the functional programming way". There may be more "perly" solution that are more succinct (I don't mean golf !), efficient and so on. You are welcome to propose other methods and / or observations.

P.S: implementations in Perl 6 will be also most welcome !