[i.o.]

можно создать второй массив точно такой же длинны и внести в каждый его элемент что то вроде

{ origIndex: i,  r: Math.random() }

Потом его отсортировать по полю "r"

arrRnd.sortOn( "r", Array.NUMERIC );

и считывать рандомный неповторяющийся элемент уже из первоночального массива со строками как

var myString:String = arrOrig[arrRnd[i].origIndex];

В принципе, если не нужна универсальность, то вместо origIndex можно вписывать сразу значения строки. А после сортировки считывать примерно так

var myString:String = arrRnd[i].origString

Такая вот идея ))