Seed a %seen hash with identical number pairs as we don't want those; sort and join the keys for non-repeating keys to save having to keep 6:17 and 17:6. Use a do { ... } until condition to keep choosing random numbers until we find one that isn't already in the %seen hash.

knoppix@Microknoppix:~$ perl -Mstrict -Mwarnings -E '
> my %seen;
> $seen{ $_ . q{:} . $_ } ++ for 0 .. 19;
> my @pairs;
> push @pairs, do {
>    my $random;
>    do { $random = int rand 20 } until
>       not $seen{ join q{:}, sort { $a <=> $b } $_, $random } ++;
>    [ $_, $random ];
>    } for 0 .. 19;
> say sprintf q{%2d - %2d}, @{ $_ } for @pairs;'
 0 - 14
 1 - 14
 2 -  5
 3 - 10
 4 -  7
 5 -  4
 6 - 18
 7 -  2
 8 - 12
 9 -  8
10 - 14
11 - 17
12 - 18
13 - 16
14 -  6
15 - 19
16 -  2
17 - 10
18 -  1
19 - 11
knoppix@Microknoppix:~$
[download]

I hope this is helpful.