01 [
02   [[0, 0], [0, 1], [0, 2], [0, 3]],
03   [[1, 0], [1, 1], [1, 2], [1, 3]],
04   [[2, 0], [2, 1], [2, 2], [2, 3]],
05   [[3, 0], [3, 1], [3, 2], [3, 3]],
06 ]
<code>

@queue should perhaps better been named @rows. Then:
<code>
01 my $queue = Thread::Queue->new();
02 $queue->enqueue(\@rows);
03 my @threads = map { threads->create( \&process, $queue ); } 1 .. 4;
04 ...

##</code><code>##

#! perl -slw
use strict;
use threads;
use Thread::Queue;
use Time::HiRes qw[ time ];
use GD;

sub rgb2n{ local $^W; unpack 'N', pack 'CCCC', 0, @_ }

my $i = GD::Image->new( 1000, 1000, 1 );

my $start = time;
for my $y ( 0 .. 999 ) {
    for my $x ( 0 .. 999 ) {
        $i->setPixel( $x, $y, rgb2n( map int( rand 256 ), 1.. 3 ) );
    }
}
my $end = time;
printf "Filling a 1000x1000 pixel image 1-pixel at a time took: %.9fs\n", $end - $start;
#open O, '>:raw', 'junk.png'; print O $i->png; close O; system 1, 'junk.png';

my @cols;
$start = time;
for my $y ( 0 .. 999 ) {
    my @row;
    for my $x ( 0 .. 999 ) {
        push @row, [ $x, $y ];
    }
    push @cols, \@row;
}

my $Q = new Thread::Queue;
$Q->enqueue( \@cols );

async{ my $rCols = $Q->dequeue; }->join;

$end = time;
printf "Populating 1000x1000 AoAoAs and tranferring to another thread took: %.9fs\n", $end - $start;

##</code><code>##

c:\test>junk999
Filling a 1000x1000 pixel image 1-pixel at a time took: 6.491771936s
Populating 1000x1000 AoAoAs and tranferring to another thread took: 30.876082897s

##</code><code>##

# main thread
my( $X, $Y ) = ...;

for my $y ( 0 .. $Y-1 ) {
    $Q->enqueue( [ $X, $y ] );     
}

## drawing thread
while( my( $x, $y ) = @{ $Q->dequeue } ) {
    $image->setpixel( $_, $y, ... ) for 0 .. $X-1;
}

##</code><code>##

## main
for my $y ( 0 .. $Y ) {
    my @colors;
    for my $x ( 0 .. $X ) {
        push @colors, Mandelbrot( $x, $y );
    }
    $Q->enqueue( [ $Y, @colors ] );
}

### thread

while( my( $y, @colors ) = @{ $Q->dequeue } ) {
    $image->setpixel( $_, $y, $colors[ $_ ] ) for 0 .. $#colors;
}