Python's random module has a shuffle method that allows you to shuffle elements of a list. You can do something like this:
#shuffle works on lists, you have to convert your string into a list object
seq = list('AACAAAACAAAAAGTTGGGTAGTTTGAGAAC')
Probably not the most efficient way to do it if you have a very long sequence.
To do it by di-nucleotides, just break your string up into a di-nucleotide list:
seq = 'AACAAAACAAAAAGTTGGGTAGTTTGAGAAC'
seq = [seq[x:x+2] for x in range(0,len(seq),2)]
Note that for odd length sequences, the last element will be a single nucleotide. If you want to remove that, check for odd length and pop off the last element of the list.
As brent and hengli commented, this actually doesn't preserve all the di-nucleotide frequency. A more sophisticated method will be needed to do this.
I guess you can treat this problem similar to a sequence assembly. Generate k-mers with k=2 for the sequence and make a redundant debruijn graph. All possible complete traversals of this graph would be the possible shuffled sequences. Then choose a random one out of the possible traversals.
Getting complete traversals becomes a traveling salesman problem....
Brentp's solution further down is probably the best solution you can achieve without doing crazy algorithms.