Here are a few options:
Tailoring: Lightweave Embroidery (550 skill to reach) 2000 int for 15 seconds, 45 second ICD. Average 666 int vs 50 int or 65 crit for ilvl 300 cloaks.
Spellthreads: 265 int + 165 spirit or crit vs 55 int + 45 spirit or 65 stam. (Overall: 826 int increase on the average)
Alchemy: Vibrant Alchemist Stone: 300int + red socket (+10 int bonus) + 194 haste vs either of your current trinkets. (+360 int + 22 secondary stats, lose trinket proc - Also gain Mixology, +37 SP with Flask of the Frost Wyrm)
Leatherworking: 500 int to bracer enchant vs 50 int or 65 crit or 65 haste. Leg enchant may be nice in PvP for added stam or crit. (+450 Int increase)
Blacksmithing, Jewelcrafting, and Inscription do not grant a benefit beyond the WotLK bonuses.
Blacksmithing: 2 gem slots = 100 int.
Jewelcrafting: 3 epic cuts = +51 int over comparable gems (and if you have the gem slots).
Inscription = 125 int + 25 haste vs 24 spellpower + 15 haste - slightly better than BS.
I am not sure about Engineering, Herbalism, or Skinning, honestly.
I would recommend Tailoring for sure, with it being very close with Leatherworking and Alchemy. I would recommend doing Alchemy, since secondary stats are very strong for 80s, allowing you to keep a 65 crit or haste to the bracers.
On a side note, I wouldn't worry about sticking strictly to mail. There are some very strong ilvl 409 cloth pieces, along with a weapon that can significantly boost your dps.
Ravenclaw Harbinger alone would boost your damage more than any profession would (about a 2k spellpower increase along with better enchants).
-----
Edit: Did not see Splosion's post before posting. I do like his recommendation on Herbalism - great burst potential. I would go Tailoring/Herb based on his recommendations too.