Here's an attempt using strings ( so I can do "inner" point removal with just one s/// ) and using vr's triple idea Re: Polygon Creation -- Request for Algorithm Suggestions ( so I can "walk" the perimeter by finding the closest unused point to the previous point.

#!/usr/bin/perl

# http://perlmonks.org/?node_id=1204060

use strict;
use warnings;

my @points = points();
my ($minx, $miny, $maxx, $maxy) = (
  $points[0][0], $points[0][1], $points[0][0], $points[0][1]);

for (@points)
  {
  my ($x, $y) = @$_;
  $minx > $x and $minx = $x;
  $miny > $y and $miny = $y;
  $maxx < $x and $maxx = $x;
  $maxy < $y and $maxy = $y;
  }

my $width = $maxx - $minx + 1;
my $width3 = $width * 3;
my $gridwidth = $width3 + 1;
my $height = $maxy - $miny + 1;
my @letters = ('A' .. 'Z', 'a' .. 'z'); # label points by letter seque
+nce

my $grid = ( '---' x $width . "\n" ) x $height x 3;

for (@points)
  {
  my ($x, $y) = @$_;
  for my $xx (0..2) # triple
    {
    for my $yy (0..2) # triple
      {
      substr $grid,
        (($y - $miny) * 3 + $yy) * $gridwidth + ($x - $minx) * 3 + $xx
+,
        1, 'O';
      }
    }
  }

#print $grid, "\n\n";

$grid =~ s/          # remove "inside" points
  (?<=O)
  (?<=O.{$width3})
  O
  (?=O)
  (?=.{$width3}O)
  / /gsx;

#print $grid, "\n";

my $output = (' ' x $width . "\n") x $height;

my $i = 0;
my @answerpoints;
my @available;

push @available, $-[0] while $grid =~ /O/g;
my $previous = shift @available;
place($previous);

while( @available )
  {
  (my $closest, @available) = map $_->[0],
    sort { $a->[1] <=> $b->[1] }
    map [ $_, distance($_, $previous) ],
    @available;
  $previous = $closest;
  place($closest);
  }

print "$output\n"; # for show

#use Data::Dump 'pp'; pp \@answerpoints; # the real answer :)

sub place
  {
  my $pos3 = shift;
  my ($x3, $y3) = ( $pos3 % $gridwidth, int $pos3 / $gridwidth );
  my ($x, $y) = (int $x3 / 3, int $y3 / 3);
  pos($output) = $y * ($width + 1) + $x;
  $output =~ s/\G /$letters[$i++ % @letters]/ and
    push @answerpoints, [ $x + $minx, $y + $miny ];
  }

sub distance # between two pos values
  {
  my ($from, $to) = @_;
  my ($x1, $y1) = ( $from % $gridwidth, int $from / $gridwidth );
  my ($x2, $y2) = ( $to % $gridwidth, int $to / $gridwidth );
  sqrt( ($x2 - $x1)**2 + ($y2 - $y1)**2 ); # sqrt may not be needed
  }

sub points
  {
  ... data points removed to shorten listing
  }
[download]

Outputs (using letters in sequence to show the order of the points):

                             A          
                      MNOPQRSB          
                    KL       C          
                    J        D          
                    I        E          
 k                 H          FG       O
j l               G             HIJKLMNP
i m              F                     Q
 h no            E                     R
  g  pq          D                     S
   f   rs        C                     T
   e     tuvw    B                     U
   d         xyzA                      V
   c                                   W
   baZ                                 X
      Y                                Y
      X                                Z
      W                                a
       V                               b
       U                               c
       T                               d
        S                              e
        R                              f
        Q                              g
         P                            h 
          ONMLK                       i 
               JIHGFED                j 
                      CBAz            k 
                          yxwvut      l 
                                s    m  
                                rqpon
[download]

Of course, the "real" answer is in @answerpoints (not shown because of length)