We all have zones that we're disappointed in, or at least think could have been better. Post what you'd have changed about them here. Here's my ideas for a goblin-less Azshara:
The beginning of the zone is pretty much the same, with the Horde beginning lumber operations and the night elves fighting them.
When you get up to Lake Mennar, a naga is ordering around some murlocs. The naga drops a note from his superiors with cryptic messages about water elementals and Neptulon, foreshadowing the plan in Vashj'ir. An orc at the Orgrimmar gates sends you against the naga in Azshara's southeastern corner, near the Ravencrest Monument and surrounding areas.
You run into Duke Hydraxis battling a naga commander, and the naga overpower and kidnap him. Hydraxis begs you to find help.
One of the nagas' murloc slaves appears when you return to Orgrimmar's gates, having run away from them, and explains that the naga are testing out mind controlling powerful elementals, though he does not know why (again, foreshadowing Neptulon). He recommends you go find Arkkoroc to help save Hydraxis.
The Temple of Arkkoran has been destroyed by the Cataclysm, and Arkkoroc and his sea giant sons are fighting the naga which are also trying to kidnap him for their mind control tests. After fighting off the naga, Arkkoroc agrees to help you.
Arkkoroc, his sons, and the Hydraxian Waterlords assault the Ruins of Eldarath while you sneak in with the murloc who helped you earlier and spark a rebellion within the murloc slaves, pinning the naga between three enemies. Duke Hydraxis is freed before a Merciless One can be placed on his head, but the naga summon a giant faceless one. Arkkoroc and Hydraxis help you in the climax of the zone.
For the Kalecgos chain there wouldn't necessarily be any changes except where you first meet up with Kalec.
There'd also be some involvement at Bear's Head with the Timbermaw fighting fire elementals that have come down from Hyjal. Hamuul could appear on his way up to meet Malfurion.
I don't see any reason to change the night elf stuff leading into Ashenvale either.