The former, like Casey did with the ground chunks. He used precreated images, so for the background music you would want something familiar in a specific area, but having a pool of base and melody loops it still differs every playthough.
I think the sfxr and bfxr you linked are great for sound effects but not really for music. One precedureally music generator is this website
http://abundant-music.com/ which works but a bit to random maybe.