Not indexed, but a regex should search an 8k string pretty fast.

my $AoA = pack 'C*', map @$_, @AoA;

my $omit = $AoA[0];

my $pat = '[^'.( join '', map quotemeta, pack 'C*', @$omit ).']{4}';
my $re = qr/\G(?:.{4})*?($pat)/s;
my @matches = map [ unpack 'C*', $_ ], $AoA =~ /$re/g;
[download]

The following avoids recreating the original arrays at the expense of two bytes per element of @AoA.

my $AoA = pack '(C4S)*', map { @{ $AoA[$_] }, $_ } 0..$#AoA;

my $omit = $AoA[0];

my $pat = '[^'.( join '', map quotemeta, pack 'C*', @$omit ).']{4}';
my $re = qr/\G(?:.{6})*?$pat(..)/s;
my @matches = @AoA[ map unpack 'S', $AoA =~ /$re/g ];
[download]