I have Centrafuse play all my music on random. I have a playlist called All that contains all songs which I play on random. Every time I add more music I have to manually update the playlist which takes me a while to do because I find Centrafuse's playlist controls confusing. I would tell you how I do it but I can't remember.
I have actually figured out how to get Centrafuse to play all my songs on random without the playlist. When your in the music screen, at the bottom of the list that has Artist, songs etc. Open up "Music directory" or w/e and then just hit the play button. Mine, not sure about yours will star playing the first song in the list of 2800 song and i can set it to random and be done with it.