<ul id="minhaLista">
    <li><img src=... /></li>
    <li><img src=... /></li>
    ...
</ul>

var ul = $("#minhaLista");
var lis = $.makeArray(ul.children().detach()); // Remove todos os lis e converte num array
for ( var i = 0 ; i < lis.length ; i++ ) {
    var proxima = Math.floor(Math.random()*(lis.length - i) + i); // Sorteia um
    ul.append(lis[proxima]); // Coloca de volta na lista
    lis[proxima] = lis[i];  // Retira ele dos "ainda não sorteados"
}

var ul = $("#minhaLista");
var lis = ul.children();
var sorteada = Math.floor(Math.random()*lis.length);
for ( var i = 0 ; i < sorteada ; i++ )
    lis.eq(i).detach().appendTo(ul);

/**
 * Shuffle Fisher-Yates algorithm
 *
 * @see http://sroucheray.org/blog/2009/11/array-sort-should-not-be-used-to-shuffle-an-array/
 * @param   {Array}   array
 * @returns {Array}
 */
function shuffle (array) {
    var i = array.length, j, temp;
    if (i === 0) {
        return array;
    }
    while (--i) {
        j = Math.floor(Math.random() * (i + 1));
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    return array;
}

/**
 * Para um elemento pai e um array contendo nomes de arquivos, adiciona randomicamente filhos a este pai.
 *
 * @param   {DOMElement}   el      Elemento pai. Ex: document.getElementById('id-do-elemento'), jQuery('#id-do-elemento')
 * @param   {Array}        array   Array contendo a parte que muda do local da imagem
 * @param   {String}       [base]  Base do caminho
 * @returns {DOMElement}
 */
function randonImgAppendChild (el, array, base) {
    var i, base = base || '', img;
    array = shuffle(array);

    for (i = 0; i < array.length; i += 1) {
        img = new Image(); // Imagem. Poderia ser qualquer outro elemento
        img.src  = base + array[i];
        el.appendChild(img);
    }
    return el;
}

randonImgAppendChild(document.body, ['1.jpg', '2.jpg', '3.jpg', '4.jpg', '5.jpg', '6.jpg', '7.jpg', '8.jpg', '9.jpg', '10.jpg'], '/pasta/base/');
randonImgAppendChild(document.getElementById('mainbar'), ['1.jpg', '2.jpg', '3.jpg', '4.jpg', '5.jpg', '6.jpg', '7.jpg', '8.jpg', '9.jpg', '10.jpg'], '/pasta/base/');

1.jpg, 2.jpg e assim por diante.

var totalCount = 10;
function ChangeIt(){
  var num = Math.ceil( Math.random() * totalCount );
  document.getElementById("bannerRandom").style.backgroundImage = "url('/images/"+num+".jpg')";
}

$randomImg = ['img1.jpg', 'img2.jpg', 'img3.jpg', 'img4.jpg', 'img5.jpg', 'img6.jpg', 'img7.jpg', 'img8.jpg', 'img9.jpg', 'img10.jpg'];
shuffle($randomImg);
echo $randomImg[0];