Music Player with a smart Shuffle option
There's an App called "Just Playlists" that states the "none repeating shuffle" as one of its features:

http://www.androidzoom.com/android_applications/media_and_video/just-playlists_byqz.html