A solution using a Guttman Rosler Transform which might be more efficient if there are a large number of rectangles.

use strict;
use warnings;

use feature qw{ say };

my @x     = ( 3, 2, 4, 0, 3, 0, 4, 0, 3, 2, 0, 4 );
my @y     = ( 0, 0, 0, 1, 1, 0, 3, 3, 3, 3, 2, 2 );

my @rects =
   map { [ split m{:}, substr $_, 8 ] }
   sort
   map { my $packed
         = ~ ( pack q{N}, $x[ $_ ] )
         . pack q{Na*}, $y[ $_ ], join( q{:}, $x[ $_ ], $y[ $_ ] )
      }
   0 .. $#x;

my $n = 0;
say qq{@{[ sprintf q{%2d}, $n ++ ] }: @$_} for @rects;
[download]

The output.

 0: 4 0
 1: 4 2
 2: 4 3
 3: 3 0
 4: 3 1
 5: 3 3
 6: 2 0
 7: 2 3
 8: 0 0
 9: 0 1
10: 0 2
11: 0 3
[download]

I hope this is of interest.

Update: Simplified decoration/de-decoration removing need for join and split.

use strict;
use warnings;

use feature qw{ say };

my @x     = ( 3, 2, 4, 0, 3, 0, 4, 0, 3, 2, 0, 4 );
my @y     = ( 0, 0, 0, 1, 1, 0, 3, 3, 3, 3, 2, 2 );

my @rects =
   map { [ unpack( q{N}, ~ $_ ), unpack( q{x4N}, $_ ) ] }
   sort
   map { my $packed
         = ~ ( pack q{N}, $x[ $_ ] )
         . pack q{N}, $y[ $_ ]
      }
   0 .. $#x;

my $n = 0;
say qq{@{[ sprintf q{%2d}, $n ++ ] }: @$_} for @rects;
[download]

use strict;
use warnings;

# our data in arrays
my @rect_x = (3,2,4,0,3,0,4,0,3,2,0,4);
my @rect_y = (0,0,0,1,1,0,3,3,3,3,2,2);

# create an array 0,1,2,3,....as long as my data is
my @unsorted = 0..$#rect_x;

# these indexes we sort by Y and then reverse sort by X
my @sorted = sort { $rect_x[$b] <=> $rect_x[$a] } 
             sort { $rect_y[$a] <=> $rect_y[$b] } 
             (@unsorted);

my $n = 0;
for my $i (@sorted){
    print "$n $i \t $rect_x[$i] $rect_y[$i]  \n";
        ++$n;
}
[download]

yields:

$ perl lowest_sort.pl 
0 2       4 0  
1 11      4 2  
2 6       4 3  
3 0       3 0  
4 4       3 1  
5 8       3 3  
6 1       2 0  
7 9       2 3  
8 5       0 0  
9 3       0 1  
10 10     0 2  
11 7      0 3
[download]

G'day Ppeoc,

Here's my take on this:

#!/usr/bin/env perl

use strict;
use warnings;

my @rect_x = (3,2,4,0,3,0,4,0,3,2,0,4);
my @rect_y = (0,0,0,1,1,0,3,3,3,3,2,2);
my @point_x = (0) x @rect_x;
my @point_y = (0) x @rect_x;

my @sorted = sort { 
    $b->[0] <=> $a->[0] || $a->[1] <=> $b->[1]
}
map {
    [ $rect_x[$_], $rect_y[$_], $point_x[$_], $point_y[$_] ]
} 0 .. $#rect_x;

use Data::Dump;
dd \@sorted;
[download]

Output:

[
  [4, 0, 0, 0],
  [4, 2, 0, 0],
  [4, 3, 0, 0],
  [3, 0, 0, 0],
  [3, 1, 0, 0],
  [3, 3, 0, 0],
  [2, 0, 0, 0],
  [2, 3, 0, 0],
  [0, 0, 0, 0],
  [0, 1, 0, 0],
  [0, 2, 0, 0],
  [0, 3, 0, 0],
]
[download]

#!/usr/bin/perl
use strict;
use warnings;
#=====================================================================
+=====
{package point;

  sub new {return bless {x=>$_[1], y=>$_[2]}, __PACKAGE__;}
  sub Print {
     my ($self) = @_;
     return "(" . $self->{x} . "," . $self->{y} . ")";
  }

1;
}
#=====================================================================
+=====
{package rect;

    sub new {
       # Takes 2 'point's 
       return bless {p1=>$_[1], p2=>$_[2]}, __PACKAGE__;
    }

1;
}
#=====================================================================
+=====

my @rect_x = (3,2,4,0,3,0,4,0,3,2,0,4);
my @rect_y = (0,0,0,1,1,0,3,3,3,3,2,2);
my @rectangles;
# Create the 'rect' objects, and collect in @rectangles
for my $idx(0..$#rect_x){
  push @rectangles, rect::->new(point::->new($rect_x[$idx], $rect_y[$i
+dx]), undef);
}

@rectangles = sort {
                        $b->{p1}{x} <=> $a->{p1}{x} ||
                        $a->{p1}{y} <=> $b->{p1}{y}
                   } @rectangles;

for (0..$#rectangles){
    my $r = $rectangles[$_];
    print "Rectangle ", ($_+1) , " -> ",
      $r->{p1}->Print(), "\n";
}
[download]