I would recommend the Gigabeat S, it's still on c|net's Top 5 Mp3 players
but it's very hard to get a hold on since they don't make it anymore
a lot of the newer MP3 players only come with USB charging but have an AC power as an accessory
you can get like a Vision M or Archos 404 for around $150 refurb or $200 new if you look around