use Algorithm::Loops qw( NestedLoops );

sub comb {
   my @rv;
   NestedLoops(\@_, sub { push(@rv, [ @_ ]); });
   return \@rv;
}
[download]

Test harness:

my $comb = comb([qw(a b c)],[qw(1 2 3)],[qw(- + *)]);

require Data::Dumper;
print(Data::Dumper::Dumper(
   comb([qw(a b c)],[qw(1 2 3)],[qw(- + *)])
));

print(scalar(@$comb), "\n");  # 27
[download]

Update: What follows is a solution that doesn't require an external module. Neither it nor NestedLoops are recursive. Since they're not recursive, they're probably faster, more memory efficient, and you can use a callback instead of building the result in memory. You could even convert the code below into an iterator.

sub comb {
   my @idx = map { 0    } @_;
   my @max = map { $#$_ } @_;

   my @rv;

   for (;;) {
      push(@rv, [ map { $_[$_][$idx[$_]] } 0..$#idx ]);

      my $i = 0;
      for (;;) {
         $idx[$i]++;
         last if $idx[$i] <= $max[$i];

         $idx[$i] = 0;

         $i++;
         return \@rv if $i == @idx;
      }
   }
}
[download]