So my idea was similar to Eric's, but I wanted to make it work "completely". So instead of storing references to all the divs in an array, I just decided to store an array of ints representing each div. The way I eventually select them with jQuery is "#lightbox + i", so if you don't have this exact structure (where the divs have an id like "lightbox" and an int - from 1 to the last count), then you can use .eq() or nth-child. It won't be the exact same results, but it will have the same random effect, just done in a different way. I found a function that "randomizes" an array - I'm guessing like what Eric's Shuffle does. But here's where I got it from - How to randomize (shuffle) a JavaScript array? . I had to modify it to return a new array instead of modify the one passed to the function. Also, I kept everything in the document.ready scope, instead of the global scope, so things are passed/returned a lot. It worked fine before when I had all and randomed declared globally and didn't pass them around, I just thought this would be "better" since they weren't global.
Here's the fiddle:
http://jsfiddle.net/6qYCL/1/
And here's the Javascript:
$(document).ready(function () {
    var all,
        randomed;
    all = generateAll();
    randomed = generateRandomed(all);
    $("#generator").on("click", function (evt) {
        evt.preventDefault();
        randomed = doNext(all, randomed);
    });
});
function generateAll() {
    // Generates the array of "all" divs to work on
    var a = [];
    var divs = $(".hide > div.lightbox");
    for (var i = 1; i <= divs.length; i++) {
        a.push(i);
    }
    console.log("List of divs available to toggle: " + a);
    return a;
}
function generateRandomed(all) {
    // Randomizes the original array
    randomed = fisherYates(all);
    console.log("Setting randomized array: " + randomed);
    return randomed;
}
function doNext(all, randomed) {
    $(".lightbox, #last-div").hide();
    if (randomed.length < 1) {
        console.log("All lightboxes toggled, showing last, then starting over");
        $("#last-div").show();
        randomed = generateRandomed(all);
    } else {
        var next = randomed.shift();
        var selector = "#lightbox" + next;
        console.log("Showing " + selector);
        $(selector).show();
        console.log("What's left: " + randomed);
    }
    return randomed;
}
// Randomizes an array and returns the new one (doesn't modify original)
function fisherYates ( myArray ) {
  var return_arr = myArray.slice(0);
  var i = return_arr.length;
  if ( i == 0 ) return false;
  while ( --i ) {
     var j = Math.floor( Math.random() * ( i + 1 ) );
     var tempi = return_arr[i];
     var tempj = return_arr[j];
     return_arr[i] = tempj;
     return_arr[j] = tempi;
  }
  return return_arr;
}
It accounts for getting to the end of the list and display #new-div like you mentioned, then starting the process over. If you look in your browser's console, you can "watch" what's happening during initialization and when clicking the link.
I think this is close to what you were looking for. I'm not sure which is a better solution - storing references to the elements or just an array of ints to loop through and eventually find. I know there are many variations on how to do this - when/how to store the counting stuff, when/how to randomize the array or retrieve a random value (and how to keep track of which has been used), where to store all references, and plenty more. I hope this at least helps!