If you're using the "least recently played" version of the shuffle, then appending followed by reshuffling will do what you want, and the songs you recently heard will be weighted towards the bottom of the shuffle.