It is always hard to answer "What if" questions about the novel, because Suzanne Collins chose Peeta for a reason.
Katniss and Gale are very similar people. They both hate the capitol instinctually and want to exact revenge against it. Peeta is better apt to play along and charm the Capitol like in the interiew situation. Neither Gale nor Katniss want anything to do with an experience like that. Peeta better balances Katniss with his honesty and naivete about the Capitol and world. He grew up among the middle-class of District 12.
As for how it would be different, first of all, it would have been more difficult for Katniss to leave her mother and Prim in the Seam. She would not have the comfort knowing that Gale would be in District 12 ensuring they were taken care of and well-fed.
I think Gale and Katniss would have teamed up from the beginning, because they instinctively trust each other. There would have been more of an internal conflict regarding their team as Katniss would know it could not last. I am not sure if they would think to play up the romantic angle, because that charming, pandering to the audience act comes from Peeta.
I would also think about how Rue might fit into the equation. Her relationship with Rue is really important to her development in the arena and understanding the idea of not losing ones' identity in the arena. But, with Gale at her side, would Katniss have been able to allow a third person into their alliance?
This would make a good discussion topic. Consider adding a discussion post regarding this idea.
In such cases, you can only conjecture.
I agree with everything that sarahc418 has said.
Maybe Katniss would not have won since they only let Peeta and her live because they thought they were lovers.
Maybe a whole rebellion would not have started?
Maybe there wouldn't have been a Quarter Quell in which old winners had to get in?
Who knows? :)