The tools that you tried are designed to give you all permutations without repeating the same sequence, so they will go methodically one by one, if all you want are a few random shuffles you can easily generate them directly in most programming languages, a Python solution would look like so:

import random

seq = list("ATAAAAGGATCCCCAC")

for step in range(10):
    random.shuffle(seq)
    print ''.join(seq)

---------- Python ----------

CTAAACCGCATAGACA
CCAACTAAGATGACCA
GACCACTCGTCAAAAA
ACAAAGCTATAGACCC
CAAGGATCCACCATAA
ACATCAAGACAATCGC
AGCTCGCCAACTAAAA
CAATGCCAACACATAG
TCAAAGAACCGATCCA
ATAGCCCACAAAACTG

Theoretically this could generate duplicate sequences but if your sequences are long the chance for that to happen is very low.

Its perhaps not exactly what you want, I'm not very clear, but SeqGen might be useful. It is particularly good if you want not entirely random changes but rather changes constrained within a biologically realistic model of mutation.

"Seq-Gen is a program that will simulate the evolution of nucleotide or amino acid sequences along a phylogeny, using common models of the substitution process. A range of models of molecular evolution are implemented including the general reversible model. State frequencies and other parameters of the model may be given and site-specific rate heterogeneity may also be incorporated in a number of ways. Any number of trees may be read in and the program will produce any number of data sets for each tree. Thus large sets of replicate simulations can be easily created. It has been designed to be a general purpose simulator that incorporates most of the commonly used (and computationally tractable) models of molecular sequence evolution."

Thanks to all the answers! I've just found a way for perl coders: the Algorithm::Numerical::Shuffle module.

e.g.

use Algorithm::Numerical::Shuffle qw /shuffle/;
my $seq = "CGATCGATCGATCGATCGTAGCTAGCTAGCT";   
my $shuf = shuffle [split(//, $seq)];

for my $i (1..5000) {    
    my @shuffled_seq = shuffle $shuf;
}