For this I'd probably go with the 'Schwartzian Transform':

my @arr = map { $_->[0] }
 sort { $a->[1] cmp $b->[1] }
 map  { [ $_, sort_key($_) ] } @arr;

sub sort_key {
 my $str = shift;
 my $first = substr($str, 0, 1) eq "X" ? "0" : "1";
 return $first . $str;
}
[download]

In fact, instead of creating an array ref, you could map a character onto the front of each string in the beginning, then map it off at the end, which would be more efficient memory-wise, not sure about time-wise, but that's left for you to figure out :-)