I don't think you need to catch another Pokemon. Just put Kirlia in front of your party (make sure the party doesn't get too crazy or illegal) and repeatedly battle her, and your Kirlia will eventually get overleveled enough to beat her.
If you really want a new Pokemon but are okay with something other than Torkoal or Skarmory, then you should get a Swellow. (you can get the already evolved ones on Route 115) Its STAB return gets pretty strong, and it has better offensive stats than both Torkoal and Skarmory. Swellow also outclasses Linoone, so you can stop using Linoone in battles and keep it as an HM slave.
If you really want either Torkoal or Skarmory, then you should get Skarmory. Torkoal is kind of useless because it's slow and water type opponents are common.