Not sure why you have an AoA with only single element sub-arrays but here's a way to do what you want.

johngg@shiraz:~/perl/Monks > perl -Mstrict -Mwarnings -MData::Dumper -
+E '
my $data = [
   [ 123 ],
   [ 789 ],
   [ 456 ],
   [ 123 ],
   [ 543 ],
   ];

my @uniq = do {
   my %seen;
   grep { not $seen{ $_->[ 0 ] } ++ }
   @{ $data };
   };

print Data::Dumper->Dumpxs( [ \ @uniq ], [ qw{ *uniq } ] );'
@uniq = (
          [
            123
          ],
          [
            789
          ],
          [
            456
          ],
          [
            543
          ]
        );
[download]

I hope this is helpful.

Update: Note that Eily's approach building a hash then using keys can also be made to work but the order of the elements is not (necessarily) preserved due to the way the hashing algorithm assigns keys to hash buckets. Because we want to preserve the array references we have to use those as the values, the keys being their content. From Perl 5.14 keys and values can take a scalar reference to a hash, as I do here.

johngg@shiraz:~/perl/Monks > perl -Mstrict -Mwarnings -MData::Dumper -
+E '
my $data = [
   [ 123 ],
   [ 789 ],
   [ 456 ],
   [ 123 ],
   [ 543 ],
   ];

my @uniq = values { map { $_->[ 0 ] => $_ } @{ $data } };

print Data::Dumper->Dumpxs( [ \ @uniq ], [ qw{ *uniq } ] );'
@uniq = (
          [
            789
          ],
          [
            543
          ],
          [
            456
          ],
          [
            123
          ]
        );
[download]