Is it possible to have, say 3 different backgrounds, and randomly assign one of the three backgrounds to the same level each time the character dies?
My first thought would be checkpoints somehow taking you to exact copies of the world you just died in except the change in background... Just a brainstorm