Nice thought. I tried this and several variations on it:

my $start = [ int( rand 500 ), int( rand 500 ) ];
my @points = map{
    my $a = rand( 2*PI );
    my $d = int( rand 500 );
    my $x = $d * cos( $a );
    my $y = $d * sin( $a );
    $x -= 500 while $x > 500;
    $x += 500 while $x < 0;
    $y -= 500 while $y > 500;
    $y += 500 while $y < 0;
    [ $x, $y ];
} 1 .. $N;
[download]

Whilst it certainly tends to create clusters, the clusters tend to be (very) evenly distributed, which doesn't trigger the worse case.