You could try this.
Curtis MP3 Player
It's 256 MB but I have a 128 mb MP3 player and it holds 60 songs once you convert your songs to WMA. So basically you'd be able to hold over 100 songs which more than anyone would need IMO.
Something I hate about the iPod shuffle is you have to get songs from iTunes which really sucks.