Erlang, 188 172 132 chars
f([H|C=[_|_]])->T=[lists:last(C)],[H|s(C--T,T)];f(X)->X. s([],N)->N;s(D,N)->E=[lists:nth(random:uniform(length(D)),D)],s(D--E,E++N).
I'm still learning Erlang so any tips on making this shorter are appreciated.
full code(string_shuffle module):
-module(string_shuffle).
-export([f/1]).
f([H|C=[_|_]])->
T=[lists:last(C)],
[H|s(C--T,T)];f(X)->X.
f(X)->X.
s([],N)->N;
s(D,N)->
E=[lists:nth(random:uniform(length(D)),D)],
s(D--E,E++N).
Edit
##Edit TookTook the shuffle part out as a seperate function which no longer requires the head and tail of the list to be passed around.
Edit 2
##Edit 2
RestructuredRestructured to remove one of the ffunction patterns, changed the shuffle function to accept only two parameters, changed lists:delete for --[], swapped a lists:reverse call for a lists:last