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

If so, the following should work:

#!/usr/bin/perl
use warnings;
use strict;

my @a = (1, 2, 3);
my @b = qw( a b );

my @expected = (
    [ [1, "a"], [2, "a"], [3, "a"] ],
    [ [1, "a"], [2, "a"], [3, "b"] ],
    [ [1, "a"], [2, "b"], [3, "a"] ],
    [ [1, "b"], [2, "a"], [3, "a"] ],
    [ [1, "b"], [2, "b"], [3, "a"] ],
    [ [1, "b"], [2, "b"], [3, "b"] ],
#   [ [1, "a"], [2, "b"], [3, "b"] ],
#   [ [1, "b"], [2, "a"], [3, "b"] ],
);

my %reverse_b;
@reverse_b{@b} = 0 .. $#b;

my @c = [ map [ $_, $b[0] ], @a ];
while (1) {
    my @indexes = map $reverse_b{ $_->[1] }, @{ $c[-1] };
    my $r = $#indexes;
    while ($r >= 0) {
        if (++$indexes[$r] > $#b) {
            $indexes[$r--] = 0;
        } else {
            last
        }
    }
    last if $r < 0;

    push @c, [ map [ $a[$_], $b[ $indexes[$_] ]], 0 .. $#a ];

}

use Test::More; use Test::Deep;

cmp_deeply \@c, bag @expected;

done_testing();
[download]

Update: I forgot to mention: It works for any size of both the arrays.

($q=q:Sq=~/;[c](.)(.)/;chr(-||-|5+lengthSq)`"S|oS2"`map{chr |+ord
}map{substrSq`S_+|`|}3E|-|`7**2-3:)=~y+S|`+$1,++print+eval$q,q,a,
[download]