I haven't played my warrior in a long time, but can you kite and AOE? I'm telling you...it can be very fast if you get it down.
Edit:
I just dusted off my 87 Warrior and headed over. I am Arms, and here is how I kill the worms:
They are yellow, so you hold the cards on the pull.
Primarily we will be using Heroic Leap, Charge, Thunderclap and Shockwave (talent)
We are setting up Shockwave for the stun so we can get in, do damage and run away to rinse, repeat.
I started by Heroic Leaping in, followed immediately by a Shockwave (which stuns), at which point you are going to want to start running away from poison spit. By this time, Thunderclap is up and you can fire that off if they start to get close. The poison spit is an easy mechanic to avoid and you can fool the little guys into stopping for you and then you can ready another leap or charge followed by a Shockwave. I kept distance and had the first wormy targeted as I ran, and when charge and shockwave are up, charge and hit shockwave. Easy!
Mess with it and you'll see what I mean. I haven't died yet and my gear is terrible. Good luck!
Sorry Edit 2:
The Mass Spell Reflection talent works to deflect back Poison Spit...and this will make it even easier. I charge in, hit spell reflect, AOE, Shockwave and start the kite.