This method uses only a single special (??{...}) expression within the RE, but unfortunately it requires that you know the named variable name of the string being passed to it. (See Update1)

my $string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
my ($random) = $string =~ m/(??{'.'x rand length $string })(.)/s;
print $random, "\n";
[download]

------------
UPDATE1: And here it is without the dependancy on knowing the name of the scalar holding the string (Thanks perlre).

my $string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
my( $random ) = $string =~ m/^(??{ '.' x rand length $_ })(.)/s;
print "$random\n";
[download]

I knew there had to be a way. ;)

------------
UPDATE2: And here it is with a quantifier instead of a huge string of '.' metacharacters. The code is longer, but it's more friendly to real long target strings.

my $string = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
my ($random) = $string =~ m/^
                            (??{'.{' . int(rand length $_) . '}' })
                            (.)
                           /sx;
print "$random\n";
[download]

Enjoy!