You can get close with two playlists.
How about:
Playlist 1:
meets SOME of the following criteria:
Playlist is Playlist A
Playlist is Playlist B
Playlist is Playlist C
(etc. for all the playlists you want to select from)
This will create a playlist from all those songs, but WITHOUT any repeats.
Playlist 2 (this is the one you sync with your iPod):
meets ALL of the following criteria:
Playlist is Playlist 1 (<--ensuring that the songs come from your chosen lists)
not played within the last 6 months
Number of songs: 500.
This won't refresh your playlist in a single go, but it will keep it fresh automatically as soon as a song has been played. The next time you connect the iPod to the computer, all songs you've heard will be exchanged for new ones, both in iTunes and on the iPod.
I.e., a refresh as soon as you re-connect.
Not *exactly* what you asked for, but certainly the next-best thing.