I came up with a way of doing both "random" and "must change" that I liked so I golfed it a bit while still keeping it strict and warnings compliant (in spirit, even):

#!/usr/bin/perl -p
#12345678 1 2345678 2 2345678 3 2345678 4 2345678 5 2345678
 s#\B(\w+)\B#join$,,(split$,,$1)[sub{my($l,@x)=@_;$l=$x[$l]
 =pop while@_;@x}->(sort{(-1,1)[rand 2]}0..-1+length$1)]#ge
# 6 12345678 7 2345678 8 2345678 9 2345678 0 2345678 1 2345
[download]

But 115 characters is rather long. Trying to golf harder, I only saved 7 strokes (108):

#!/usr/bin/perl -p
#12345678 1 2345678 2 2345678 3 2345678 4 2345678 5 2345
 s#\B\w+\B#join$,,(split$,,$&)[sub{($b,@*)=@_;$b=$*[$b]=
 pop while@_;@*}->(sort{(-1,1)[rand 2]}0..length$&)]#ge
#678 6 12345678 7 2345678 8 2345678 9 2345678 0 2345678
[download]

Anyway, I find the algorithm interesting so you might treat it like an obfu and deconstruct it. (:

I'm also curious why I need to do:

     sort {(-1,1)[rand 2]} ...
[download]

Shouldn't the following do the same thing (other than very, very rarely returning "0" for the comparison)?

    sort {-.5+rand} ...
[download]

It appears that sort (Perl 5.006_00) treats ( -1 < values < +1 ) like "0" [I expected -0.1402 to be treated like "-1" and +0.3886 like "+1"] but treats ( values <= -1 ) like "-1" and ( 1 <= values ) like "+1".

I find this rather strange. It is also quite unfortunate when golfing. :)

Update: Thanks to PhilHibbs' insight, I realized I could golf further by taking advantage of a different "convert to IV" side-effect:

#!/usr/bin/perl -p
#12345678 1 2345678 2 2345678 3 2345678 4 2345678 5 23
 s#\B\w+\B#join$,,(split$,,$&)[sub{($b,@*)=@_;$b=$*[$b
 ]=pop while@_;@*}->(sort{rand~0}0..-1+length$&)]#ge
#45678 6 12345678 7 2345678 8 2345678 9 2345678 0 23
[download]

which gets me to 103 strokes (I also realized that dropping "-1+" made it possible for words to stay unchanged).

                - tye