In terms of level selection, and the non-linear approach to the genre, have you thought about letting the player complete the levels out of order and perhaps having certain shortcuts for earlier levels be accessible with items from later levels?
Say, there is an objective on level 3. You could take the normal route to reach it, but there is also a shortcut that can be opened with a powerup aquired on level 5.
One downfall of this would be if you ran into the shortcut before obtaining the item needed, you might get frustrated that you can't progress, assuming that it was the intended path. So you would have to make the normal path "super" obvious.
As you can tell, I haven't really thought this through and I'm kinda just brainstorming out loud.