You know, they say that people living in the amazon build great tree-houses and bridges just below the canopy, and if you can get up there, you can run faster than the fastest leopard. Perhaps the life fast travel should be a hidden trail or vine swing.
Gravity, meanwhile, can be a strange area with no gravity. Just aim where you want to go and jump.
Fire is a toughy. Lava generally moves really slowly, and fire doesn't really move at all. But if there were a river of lava, maybe the right boat could cross it?
Lastly, death is simple. For their crimes against the world, a swarm of lost souls are accursed, forced into servitude. They'll get you where you want to go.