Eso garantiza la aleotoriedad pero no la no repetición. Tal vez eso se pueda subsanar, añadiendo el elemento eliminado a un nuevo array con el método unshift(). Este array tendrá los elementos con los que se rellenar el array original.
Como el índice del último elemento será 0, al comenzar la segunda vuelta, habría que asegurarse de que el número aleatorio no sea 0. Para esto se ha de usar
http://jsfiddle.net/marlanga/sg2Ja/4/