Try applying your best tests to this (and let me know how it fairs?):

Updated: String is 3 * 1e6!

#! perl -slw
use strict;
use Math::Random::MT qw[ rand ];

sub shuffle {
        return unless defined wantarray;
        my $ref = @_ == 1 ? $_[ 0 ] : [ @_ ];
        for( 0 .. $#$ref ) {
                my $p = $_ + rand( @{ $ref } - $_ );
                @{ $ref }[ $_, $p ] = @{ $ref }[ $p, $_ ];
        }
        return wantarray ? @{ $ref } : $ref;
}

my $string = 'abc' x 1e6;
my $len = length $string;
my @picks = ( shuffle 0 .. $len-1 )[ 0 .. $len * 0.1 ];

substr $string, $_, 1, '?' for @picks;
[download]