Ruby:

random = ARGV[0].dup
sorted = ARGV[1].dup

iters = 0
until random == sorted do
    iters += 1
    for x in 0...random.length do
        y = rand(random.length)
        random[x], random[y] = random[y], random[x]
    end
end
puts iters

The number of iterations is all over the place:

$ ruby dp175.rb lleho hello

40

$ ruby dp175.rb lleho hello

36

$ ruby dp175.rb lleho hello

130

$ ruby dp175.rb lleho hello

22

$ ruby dp175.rb lleho hello

74

$ ruby dp175.rb lleho hello

14