That should be possible, yes. Most players will boot into rockbox when power is switched on, and rockbox has a setting to start playing straight away if there is a current playlist.
I would avoid the ipod classic and the ipod nano 2g for this, as I believe they have a bug where for some people the player finds a USB connection for only a charger, which makes it go into USB mode, which isn't what you want. Personally I'd probably get one of the sansa players, probably a clip zip, and use a microSD card for content.
So the thing to do would be to set the "repeat" option to "shuffle" (so things don't play in the same order twice), set the "start screeen" option to "resume playback" so it starts playing on power up, and add all files to the playlist (using the recursive insert function).