Create a smart playlist with songs that have a playcount of less than 1, then you can put that on shuffle and it will play through those songs.
Alternatively, sort your library by playcount (in View- Options) if the column isn't there yet, take Shuffle off - and just play through the ones that are blank