I'm pretty sure what you want is to avoid the grapple in the first place. That's really hard because, for the most part, it's just a melee touch attack to start. So unless you're immune to being touched (possible but difficult) if you're immune to grapples before you know someone's going to grapple you, you're going to end up immune to attacks in general.
Assuming you don't want to play that game (the one, wherein, y'know, you're invulnerable to the mundane), escaping from a grapple is fairly easy, and, while harder, not getting grappled if you know it's coming is better. Here are ways of doing both. Omitted are sources providing effects under specific circumstances (e.g. in webs, underwater). The spells freedom of movement and heart of water included for completeness.
Spells
Best
- The 3rd-level runescarred berserker (Una 31-2) (minimum caster level 5) spell freedom of movement [abjur] (PH 233) for 10 min./level grants 1 creature the ability “to move an attack normally… even under the influence of… paralysis, solid fog, slow, and web,” to automatically succeed on grapple checks to resist grapple attempts and on grapple checks and Escape Artist skill checks made to escape a grapple or pin, and to move and attack normally underwater.
- The 3rd-level Sor/Wiz spell heart of water [trans] (CM 107) for 1 hour/level grants the caster a +5 enhancement bonus to Escape Artist skill checks, the ability to breathe water, and a swim speed equal to the caster’s land speed; as a swift action that otherwise ends the spell the caster gains the benefits the spell freedom of movement [abjur] (PH 233) for 1 round/level.
Other Sources by Level
Many, many spells grant bonuses to grapple checks. If a creature can get a grapple check bonus high enough to just win the opposed check, he can end the grapple. I've not listed those spells. Many spells also grant a bonus to Escape Artist skill checks. I've not listed those either. I find the 2nd-level Sor/Wiz spell unfettered grasp [ench] (RDr 118) too situational to include.
- The 2nd-level Sor/Wiz spell mountain stance [trans] (SpC 144-5) for 1 min./level grants 1 creature the ability as a free action to gain a bonus equal to the caster's level versus "attempts to grapple, lift, push, bull rush, overrun, throw, trip, or otherwise force the subject to move." Notable for the duration, lack of a caster level cap, untyped bonus, and versatility.
- The 3rd-level Sor/Wiz spell hesitate [ench] (PH2 114) as an immediate action for 1 round/level on 1 creature's failed Willpower saving throw the creature takes only 1 move action; the creature makes another saving throw each turn to end the effect. Notable for the casting time.
- The 3rd-level Sor/Wiz spell permeable form [trans] (LoM 129) as an immediate action for 1 round grants the caster the benefits of the incorporeal subtype (MM 310-1).
- The 8th-level Sor/Wiz spell ghostform [trans] (SpC 103) for 1 round/level grants the caster the benefits of the incorporeal subtype (MM 310-1).
Magic Items
Best
- The face slot item third eye freedom (MIC 141) (2,400 gp; 0 lbs.) as an immediate action 1/day grants for 1 round an effect like the spell freedom of movement [abjur] (PH 233).
- The shoulders slot item shadow cloak (DrU 101) (5,500 gp; 1 lb.) as an immediate action 3/day grants the wearer the ability to teleport up to 10 ft.
Other Sources by Price
- The armor and shield augment crystal crystal of glancing blows (least) (MIC 25) (500 gp; 0 lbs.) grants a +5 competence bonus to opposed grapple checks when the wearer's the defender and a grapple's initiated.
- The slotless item panic button (escaping) (CS 115) (750 gp; 0 lbs.) as a swift action once only grants an effect like the spell dimension door [conj] (PH 221) with a 30 ft. range that "affects whatever creature is in the square it lands in," never accounting for creatures sharing squares like during a grapple. Item goes unmentioned in errata. Check with the DM.
- The feet slot item anklet of translocation (MIC 71) (1,400 gp; 0 lbs.) as a swift action 2/day grants the wearer the ability to teleport up to 10 ft.
- The belt slot item silkslick belt (MIC 136) (2,000 gp; 0 lbs.) grants the wearer the ability to take a move action to make an Escape Artist skill check to free himself from a grapple or pin, and as a swift action 1/day it grants the wearer a +10 competence bonus to 1 Escape Artist skill check made before the wearer's next turn ends.
- The torso slot item vestment of ebonsilk (MIC 147) (5,000 gp; 1 lb.) grants an ongoing effect like the spell freedom of movement [abjur] (PH 233) to characters meeting specific requirements. Controversy: You can "establish the proper divine connection" by making 2-3 Use Magic Device skill checks. First, if needed, emulate an alignment (PH 85), picking CE, NE, or CN (DC 30); second, emulate the class feature (PH 86) Deity, Domains, and Domain Spells (PH 32) to pick Lolth as a deity like a 1st-level cleric (DC 21); third, emulate the class feature Spells (PH 32) to gain the spellcasting of a 13th-level cleric who has an open 7th-level spell slot (DC 33) that's sacrified to activate the relic power. Check with the DM; objections to part or all of this chain of events are common as the Use Magic Device skill is an interpretive nightmare.
- The torso slot item vest of free movement (MIC 198) (12,000 gp; 0 lbs.) as a swift action 3/day grants for 3 rounds an effect like the spell freedom of movement [abjur] (PH 233).
- The hands slot item scholar shadow hands (ToB 150) (15,000 gp; 0 lbs.) can grant a HD 18 creature the 5th-level Shadow Hand maneuver shadow stride [special] (ToB 80).
- The ring slot item ring of freedom of movement (DMG 231, 232) (40,000 gp; 0 lbs.) grants an ongoing effect like the spell freedom of movement [abjur] (PH 233).
- The armor special ability freedom (MIC 11) (+5 bonus) grants an ongoing effect like the spell freedom of movement [abjur] (PH 233).
Feats
There's only 1 feat you should barely consider if this is happening all the time, and that's the feat Close-quarters Fighting (CW 97). It's one feat, you'll meet the requirements, and if you've a spiked gauntlet (so you're threatening an area) you can make an attack of opportunity versus a creature that tries a grapple even if it has the special ability improved grab or the feat Improved Grapple (PH 95-6). Hitting it either stops the grapple cold or give you a bonus. You won't hit. You're a wizard. But 5% remains 5% and + something remains better than + nothing. Don't do this, though.
Your cohort, homunculus, intelligent animated dead, planar bound minion, or whatever, however, should take the feat Dutiful Guardian (DrU 50). Then you can rescue him (or not) while he's grappled instead.
Finally, if you're level 18 you can just take the feat Martial Study (ToB 30-1) and take the 5th-level Shadow Hand maneuver shadow stride [special] (ToB 80). Further, it has definite advantages as an extraordinary (rather than spell-like or supernatural) teleport ability. You can take the feat Martial Study at level 6 instead if an extraordinary teleport as a standard action is sufficient by picking the 2nd-level Shadow Hand maneuver shadow jaunt [special] (ToB 79)
No.
They get a free grapple check with a +4 bonus when you try to place them into a hazardous location. Not "so long as they're in a hazardous location and being grappled". Effectively, if they weren't in a specifically hazardous location before, and they will be after, then and only then do they get a free check. Moving them around while keeping them held them in a wall of fire is fine.
As such they certainly don't get a check every turn you move them anywhere above the ground. When do they get a check? It depends on what is accepted to be a "hazardous location".
Being carried off into the air is a hazardous location
This is fairly reasonable. Even if you're not actually going to take damage from falling, a mere 5 foot fall is likely to be inconvenient and possibly indirectly harmful (you could fall prone at the very least - that's a hazard). Regardless, being in the air arguably just hazardous because you're not supposed to be up there and can't move around normally or get down. Even if you don't buy this somewhat weak justification, doing it this way helps to avoid the weird corner cases of the second interpretation.
If this is true, then they get a free grapple check when you try to lift them off the ground. Specifically, when you move them 5 or more feet above the ground; moving them around less than 5 feet above the ground probably doesn't actually count as movement, even if that their feet are described as being off the ground due to your wrestling moves or whatever, because you can't move in less than 5-foot increments¹.
Being high enough above the ground to take falling damage is a hazardous location
This one is also fairly reasonable. If this is true, they get a free grapple check when you try to lift them high enough that you can cause them [falling] damage by letting go. By this logic, holding them over, say, a pool of acid would also grant them a free grapple check. It's just as hazardous a location as being held far above the ground, and for the same reason - they'll take damage when you drop them.
What if they won't take damage from certain falls? What if they have an extraordinary ability to reduce falling damge? Or what if they'll be falling 20 feet, but it's onto some very soft mushrooms that will cushion the landing and prevent all falling damage? They probably don't get a grapple check, but the rules are unclear.
Falling is a hazardous location
Under this interpretation, it doesn't matter how inconvenient or potentially dangerous the location is. Unless it is actually immediately² causing you damage, it's not hazardous. This also makes a certain amount of sense. They don't get a free check if while grappling you move them into a location where they're being flanked by a rogue, after all, even if that is arguably exposing them to a bunch of extra sneak attack damage.
If this is true, they get the free check when you let them go, regardless of how high you are flying (except they probably don't get a check at all if they're only 5 feet up and wouldn't be taking damage anyway). The issue with this (as mentioned in comments) is, well, this grapple check is only going to harm them. It's a free check to break the grapple. If they break the grapple, they fall anyway.
It also seems to contradict one of the examples given in the text ("when you place your foe in a hazardous location, such as [...] over a pit"), which strongly implies that it's one of the first two interpretations that are correct.
¹I don't know if this is explicitly stated anywhere.
²Meaning "before you get a turn"
Best Answer
Grappling Elementals works as Normal
Fire, Water, and Air Elementals (as a creature type) in Pathfinder have no rules that prevent grapple. Additionally, Elementals don't have rules that prevent grappling either.
To show that this is where you'd expect to see such a rule; note that Swarms have the following rule:
I'd point out that the three linked (CR 7) huge elementals have CMD 34; which is pretty good for their CR (nearly 10 higher than many other CR 7 monsters) making them rather difficult to grapple relative to the other creatures in their CR rating. This seems to hold for the elementals of other size; but I haven't performed an exhaustive check.
Conceptualizing it
Let's start by mentioning they're already solid enough to hit you with melee attacks, trip you, be stabbed by swords and shot by arrows; so if those don't bother you, you can probably stop reading.
I think given the above; if the DM doesn't want you to grapple and doesn't make Elementals Incorporeal I'd find it odd. I'd note that Oozes can often be grappled too; so simply slipping out of your grasp as you grapple them seems inconsistent. I honestly can't see this coming up.