You should definetly look at the mobiBLU B153. Cnet got this thing to play 146 hours on a single charge! It has a "repeat all" mode and a "random all" mode. It also uses USB. It comes in 512MB, 1GB, and 2GB versions and is suprisingly cheap.
There site has a lot more information. The link is below.

http://mobibluamerica.com/b153.html