the solution for n columns constructed from n-1 columns successively.

use strict;
use warnings;
use Data::Dump qw/pp dd/;


my @a = 1 .. 3;
my @b = "a".."b";
my @c =([]);                            # init one empty row 

for my $l (@a) {
   my @old = @c;
   @c =();
   for my $r (@b) {
      for my $row (@old) {
         push @c, [ @$row , [$l,$r] ];
         #push @c, [ (map [@$_], @$row) , [$l,$r] ]; # copy old-pairs 
+to new arrays
      }
   }
   #pp "old $l: ",@old;
}

warn "final:\n";
pp $_ for @c;

pp \@c;
[download]

[[1, "a"], [2, "a"], [3, "a"]]
[[1, "b"], [2, "a"], [3, "a"]]
[[1, "a"], [2, "b"], [3, "a"]]
[[1, "b"], [2, "b"], [3, "a"]]
[[1, "a"], [2, "a"], [3, "b"]]
[[1, "b"], [2, "a"], [3, "b"]]
[[1, "a"], [2, "b"], [3, "b"]]
[[1, "b"], [2, "b"], [3, "b"]]
[download]

NB: many subarray-refs repeat

do {
  my $a = [
    [[1, "a"], [2, "a"], [3, "a"]],
    [[1, "b"], [2, "a"], [3, "a"]],
    ['fix', [2, "b"], [3, "a"]],
    ['fix', [2, "b"], [3, "a"]],
    ['fix', 'fix', [3, "b"]],
    ['fix', 'fix', [3, "b"]],
    ['fix', 'fix', [3, "b"]],
    ['fix', 'fix', [3, "b"]],
  ];
  $a->[2][0] = $a->[0][0];
  $a->[3][0] = $a->[1][0];
  $a->[4][0] = $a->[0][0];
  $a->[4][1] = $a->[0][1];
  $a->[5][0] = $a->[1][0];
  $a->[5][1] = $a->[1][1];
  $a->[6][0] = $a->[0][0];
  $a->[6][1] = $a->[2][1];
  $a->[7][0] = $a->[1][0];
  $a->[7][1] = $a->[3][1];
  $a;
}
[download]

if you want to avoid this, swap the comments in the push lines.

update

added version with tuple copy for non-shared refs

update

toggle the loops to have the order you (probably) wanted

   for my $row (@old) {
      for my $r (@b) {
[download]

final:
[[1, "a"], [2, "a"], [3, "a"]]
[[1, "a"], [2, "a"], [3, "b"]]
[[1, "a"], [2, "b"], [3, "a"]]
[[1, "a"], [2, "b"], [3, "b"]]
[[1, "b"], [2, "a"], [3, "a"]]
[[1, "b"], [2, "a"], [3, "b"]]
[[1, "b"], [2, "b"], [3, "a"]]
[[1, "b"], [2, "b"], [3, "b"]]
[download]