Spirit, in fact only the waves of enemies have random but many mix build levels that play very different. Also it's in my opinion one of the best game on iPad, but probably on iPhone too (but I played mostly only the iPad version).
HWR Monster dash (wait a moment... I just realised you said aside from this... [self-proclaimed fail]) Veggie Samurai Fruit ninja The Incident Pix'n rush Gravity runner Above Minigore Bit pilot Chop chop runner All are on my phone and most I play regularly
Lots of good roguelikes on the device: (which are all random or mostly-random with some fixed elements) Sword of Fargoal Rogue Touch Cavern 100 Rogues Powder Rogue Nethack iNethack Slash'EM
Yeah I'm a fan of Spirit, cool it remind you. In fact I don't think Osmos have random levels but the system is so dependent of the actions you are doing that a same level can evolve in many different ways.
