You've been told a lot of confusing and outright wrong information already so let me see if I can help clear some of this up.
First off, 2/2 str haste gems arent a terrible choice. 2/2 str stam gems might be a bit better though, considering how much of a hit secondaries take in BGs. That said, as a fury warrior you're gonna be getting dual crusader Ignore Pains pretty commonly so being beefy isnt gonna be too much of a concern. FWIW I've been able to stack enough haste without the gems. Your mileage may vary.
My recommendation would be to get haste from gear and gem for either straight strength or str/stm, depending on how squishy you feel in BGs. Gun to my head, I'd tell you maybe an even mix of the two? We're all guessing about how thats gonna feel right now but I'm planning on keeping the +3s I have (6) and replacing the talasites with 2/2s
To get these gems, I'd recommend following Gobolords insanely useful
F2P JC Guide. You can safely ignore these goobers telling you you need Dragons Eyes or implying that F2P cant get the str/stam gems. You make Bold Cardinal Rubys for the +3 str or Sovereign Dreadstones for the str/stm so also, no you dont have to keep northrend JC for the gems to work.
What you will need to do is start with mining/JC and just mine and prospect your ass off until you have enough of the tier 2 gems to do all the transmutes you want to do (folks recommend wintergrasp, I recommend Sholazar Basin). Then swap to herb/alchemy and farm herbs to level alch. Recommend get another 10-15% more herbs on top of the guides recommend. RNG is a bitch.
Re: specifically Cardinal Ruby - Make sure you have enough alchemy mats to get to 75 comfortably and also transmute 5 other epic gems (hey, dreadstone!). The Cardinal Ruby transmute is locked behind a quest that requires you to transmute 5 epic gems. This quest is also often glitched! and wont appear visible so you might need to get a GM to put it in your logs for you.
Then its just a matter of slogging through a 24 hour CD on the alchemy transmute for every gem. It sucks, but what are you gonna do? You can use that month to do the JC dailies to get the recipes you need and you can also use your second prof slot to grind up more ore/gems for leveling JC and eventually engi, etc.