Is doodlejump actually random levels? Or did they just design enough to give the illusion that it is random? Can you even do random levels on iOS? I assume if you can do it on SNES anything is possible on iOS right?
This is no OS question, this is a question of game design. Of course are random levels possible. With any platform. But Doodle Jump is a good example for an endless level mode gameplay - these "levels" have no end. It's all about how far you can get and what score you reach. The obstacles inside a level are randomized.
Like FancyFactory said, it's possible, and it's what Doodle Jump does. It's known as "procedural generation". Here is the wikipedia article on the subject. In fact, It can be done for more that just levels. I believe Tiny Wings uses it for the graphics, that's how they change daily.