//first create your array with songs
var songsArray:Array = new Array();
songsArray.push("Various Artist - Song1.mp3");
//...etc
 
//next create random array
for (var i:int = 0; i < songsArray.length; i++) 
{
    pickArray[i] = i;
}
//and sort it with your custom sort function
pickArray.sort(randomSort);
 
function randomSort(elementA:Object, elementB:Object):int 
{
    return Math.random() * 10 - 5;
}
 
//let say playNextSong function is initiated 
//by the user clicking on "next" button
var counter:uint = 0;
function playNextSong(e:MouseEvent):void
{
	//pick some random song but make sure we won't go out of range
	counter = (counter == songsArray.length - 1) ? 0 : counter + 1;
	playSong(songsArray[pickArray[counter]]);
}