Step back.

Ask yourself if your code is actually too slow for your purpose. Only if the answer is "yes", continue.

Before you optimize, benchmark your code. After you did an optimization, benchmark again. Did it get faster? If not, revert.

After each optimization step, ask yourself if the code is now fast enough for your purposes. If yes, stop.

Use a profiler to find the slow parts of your program.

After this section on general optimization technique, I'll now propose a hash-based, on-pass solution. You tell me if it's faster or not. (I can't know, because I don't have real test data; four arrays aren't enough to do any serious performance analysis).

my %uniq;
my @new_AOA;
foreach my $A (@$AOA) {
    my $key = $A->[1] . '-' . $A->[3];
    push @new_AOA, $A unless $uniq{$key}++
}
[download]

Using grep instead of the loop might or might not be faster.

Update: grep version:

my %uniq;
my @new_AOA = grep {
    !( $uniq{$A->[1] . '-' . $A->[3]}++ )
} @AOA;
[download]

(Untested, but you get the idea).

And finally it's a good idea to name variables by what they contain, not by the structure of what they contain.

Not entirely sure, but (just for completeness) is your grep version supposed to sub the $A with $_ to eliminate the for loop and replace it with the grep?

So final, quickest version:

my %uniq;
my @new_AOA = grep {
    !( $uniq{$_->[1] . '-' . $_->[3]}++ )
} @AOA;
[download]

You are nearly there with the hash idea, but missed a simplification. Just step through your AoA in one loop and store the keys in a separate hash. If you find a duplicate, delete the Array entry (or whatever else you want to do with duplicates):

my %found;
my $i=0;
while ($i<@$AOA) {
  my $key = $A->[1] . '-' . $A->[3];
  if (exists $found{$key}) {
    splice(@$AOA,$i,1);
  }
  else {
    $found{$key}=1;
    $i++;
  }
}
[download]

(Untested code). If you need to do some processing of the deleted item, change above line to my $deleteditem=splice(@$AOA,$i,1);.

UPDATE: Thanks go to moritz for detecting that I forgot to increment $i. Corrected

I doubted that repeated splice on a long array is efficient (because arrays are stored as continuous memory in perl, and splice requires copying the remainder of the array), so wrote a small benchmark:

use 5.010;

my @a = map int(10 * rand), 1..1000;

sub d_grep {
    my @copy = @a;
    @copy = grep { $_ % 2 == 0 } @copy;
}

sub d_splice {
    my @copy = @a;
    my $i = 0;
    while ($i < @copy) {
        if ( $copy[$i] % 2 == 1 ) {
            splice @copy, $i, 1
        } else {
            $i++;
        }
    }
}
use Benchmark qw(cmpthese);

cmpthese -2, {
    grep   => \&d_grep,
    splice => \&d_splice,
};
__END__
         Rate splice   grep
splice 2003/s     --   -49%
grep   3900/s    95%     --
[download]

I intentionally used in-place edits in both cases, so that the two implementations remain comparable. If you find some flaws in the benchmark, please let me known - writing benchmarks isn't my particular strength :-)

For longer arrays the difference in speed grows.

Perl 6 - links to (nearly) everything that is Perl 6.

May I answer this with your own words ;-) :

Ask yourself if your code is actually too slow for your purpose. Only if the answer is "yes", continue.

Perhaps I should mention that I interpreted his 'efficiency' more in terms of efficient coding than speed (which could be the wrong interpretation)