If you're happy to overpay a LOT, check out the Sandisk Sansa Clip. They've been discontinued by the manufacturer, sadly.

When mine broke after about 5 years I replaced it with a used iPod Classic, which you can get pretty cheap but doesn't meet your requirements.