Along the lines of Juerd's code, but with implicit recursion and much less array index math (which I hate with a passion):

sub menu {
    my ($title, @option) = @{ shift };
    my (@name, @action);

    ($name[@name], $action[@action]) = splice @option, 0, 2
        while @option;

    while(1) {
        print "\n$title\n";
        print map "$_. $name[$_ - 1]\n", 1 .. @name;
        print '> ';

        chomp (my $choice = readline *STDIN);
        if ($choice and $choice > 0 and $choice <= @action) {
            my $do_action = $action[$choice];

            return unless defined $do_action;
            $do_action->() if 'CODE' eq ref $action;
            $menu($action) if 'ARRAY' eq ref $action;

            require Carp;
            Carp::croak "I don't know what to do with $action";
        } else {
            print "Invalid choice: $choice\n"
        }
    }
}
[download]

Now you can still very similarly say

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

sub foo { print "FOO!\n" }
sub bar { print "BAR!\n" }

sub menu { ... }

my ($mainmenu, $submenu);

$submenu = [
    'Submenu',
    'Bar',                  => \&bar,
    'Back to previous menu' => undef,
];

$mainmenu = [
    'Main menu',
    'Foo'        => \&foo,
    'Submenu...' => $submenu,
    'Exit'       => undef,
];

menu($mainmenu);
[download]

but you can also much more concisely say

menu([
    'Main menu',
    'Foo'        => \&foo,
    'Submenu...' => [
        'Submenu',
        'Bar',                  => \&bar,
        'Back to previous menu' => undef,
    ],
    'Exit'       => undef,
]);
[download]

Makeshifts last the longest.