iTunes shuffle settings

When using shuffle on iTunes I would like it to reshuffle everytime I double click on a song to play. For instance if I click to play song x and song y come after it, if I click to play song x again at a later time, song y is always after it. I have deduced that iTunes seems to order all your song in some random order when shuffling, and this "random" order is never changed until you quit iTunes (or take shuffle off idk which). Is there any way to make it change the song order every time I double click on a song?

Its really annoying when I have a song of the week and I click to play it and then an hour later, I click to play it again and it replays all of the song I just listened to for the past hour over again in the same order :/.

I understand how iTunes shuffles, it just does not work well with my listening habits. What I would like is a Grooveshark type shuffle option. Grooveshark plays songs randomly (without repeating) but you can also add in songs of your choosing at any time and they do not mess up the randomness of the songs you get. I was wondering if there was a way to accomplish this in iTunes. So iTunes will keep track of songs you have played and songs you have not played. When you play a song, it goes into the played list. If you play a song that has already been played, it stays in the played list. Then when iTunes needs to pick another song for you to play, it can just grab it from the list of unplayed songs. I do not think that would be too hard to implement and much better than what they have now.