I like this monk! Of course, it would only work in a campaign that also had a more powerful fighter and a few other classes.
Why? I mean, this monk falls into about the Crusader/Warlock power range. If there's a problem with the power with this monk, then you're not gonna be able to use the Fighter anyways against the likes of the Cleric, or most of the classes anyways.
I wasn't complaining about the power level. Just pointing out that this monk is much more powerful than the other basic melee classes (fighter, barbarian, rogue). Because of that, it would work best (I should have said "work best," not "only work") in a campaign where the other melee classes have been adjusted as well.
The flight and such are taken from the stereotypical Asian martial arts film, think Crouching Tiger, Hidden Dragon. Those characters would be mid-level Monks. More specifically, this class is designed around movement, and anything that cannot fly is not mobile enough. It starts with making ground movement easier (by using Balance), and ends up making flight possible. The part about balance checks being useless eventually: no, they don't. It still takes a balance check to do the swift action teleport.
Crouching Tiger, Hidden Dragon was what I was thinking about too. In that movie, the characters make tremendous leaps, but they only fight high in the air for a few seconds. It just seems like a long time because of the slow motion. Also, they're not flying around with perfect mobility; they're continuing a very long jump (equivalent to poor maneuverability). Limiting these abilities to one round, I think, would be more in line with the stereotype you're looking at.
Balance checks: If I were playing this monk, I would think: Do I want to invest a ton of skill ranks in Balance, when in the long run, it will only be useful for a single ability at high level, or would I rather distribute my skill points in other ways? If you want Balance to be important to the build, I think you should keep the many uses of it, rather than make each use expire after a few levels. Eventually, those checks won't matter anyway (especially if you let the monk take 10), but the player at least won't feel like he's wasted skill ranks.
It would also be nice if the other mobility skills were important to the build somehow. You didn't like the ideas I suggested for jump and climb, but maybe the monk could have some other use for high ranks in those skills. That would continue the theme of a super-mobility class.
If I were designing this class (which I'm obviously not), I might make the abilities something like this, with powers divided up by level. This feels less magical, and might be more in line with martial arts movies:
The monk can use mobility skills to great effect. He can jump, climb and balance with no movement penalty.
Jump: There are no limits to height and distance travelled using jump, and jumps can be made from a standing start. At at level X, the distance and height jumped are doubled, and at level Y, they are quadrupled. He can use terrain to extend a jump. For example, he can leap off the ground, then kick off a tree to jump again. At level Z, the monk can even kick off the air itself, making up to one turn of up to 90 degrees during any jump. A monk with flight from any source can make a DC30 jump check to move with mobility one step better than usual, or to fly at his land speed.
Climb: The monk can move at full speed while climbing, and can climb surfaces that are ordinarily unclimbable (a wall of force, for example). He can also use a climb check to walk along walls and even ceilings, as long as he ends his movement either holding on to something, or standing on a solid surface.
Balance: As per your description - balance to walk on water, tree branches, etc. Balance to teleport. The only change is that you have to end your movement on a solid surface when trying to walk on a surface that can't hold your weight.