There are two buttons my screenless iPod shuffle really needs: Next Track and More Like This. For any track, there are multiple axes which are "like this," and - in order of approximate significance - they are: same album+artist, same album, same artist, same playlists, same year+genre, same genre. When I'm listening to my shuffle, if I don't like a track I can hit Next. If I like a track, I should be able to hit More Like This, and pivot on the track to go on to play the album, or hit More Like This again to go to artist, or again to just focus on that genre. Then, if I don't like the track, hit Next to return to shuffle mode again.
Or maybe a better interface would be this: The shuffle should have two slider controls: volume and more/less like this. Don't like a track? Hit Less Like This and the next track is more randomised. Like a track? Hit More Like This are the next track is more likely to be from the same genre--hit it again and it's more likely to be from the same artist, the same album, share a BPM. The interactions should be: squeeze the shuffle for More Like This (it's a hug), tug the shuffle so it pulls on the lanyard for Less Like This (it's a flushing action).
cf. What I wrote about my shuffle before.