I've just got (actually I bought it in July but it's only just arrived) a Samsung YP-MT6, which is a 1GB MP3 player about the size of my thumb, which takes a AA battery, is a Mass Storage device with USB connection and seems pretty well specced and sounds reasonable. The battery lasts forever (great for me as I'm not always near a power supply) but the drawback for you is that it needs a USB-MiniUsb cable to dock to a PC. It also appears to be discontinued. Mine came from Aria and cost £45, but you might get one on Ebay...