Really verbose and a bit machiavellic, but works:

use strict ;
use warnings ;

my $string = "This is a not so random string" ;
my $randomized ;

{
  my @chars  = $string =~ /./g ;
  my %randindex ;

  for (my $i = 0 ; $i <= $#chars ; $i++) {
    $randindex{rand()} = $i ;
  }

  $randomized = join "",map $chars[$randindex{$_}], sort keys %randind
+ex ;
}

print "$randomized\n" ;
[download]

It seems to do what you asked for:

$ for I in 1 2 3 4 5 ; do perl randomize_string.pl ; done
dsg Tosnirtan sis  r maton oih
 nomira sr s dh tiansiotoTgn s
most g air dsi Tnrs  anhnitoos
 tinradoo issaosh  siTnt  rmgn
t n ssa hsgni tdrmosna Tiroio
[download]

Ciao!
--bronto

# Another Perl edition of a song:
# The End, by The Beatles
END {
  $you->take($love) eq $you->make($love) ;
}