Fire and Rock types you can deal easily with Vibrava and Serperior, respectively, shouldn't be a problem, I think. As I see your team relies too much on Flygon, so you need to have alternatives if it goes down while battling.
I would advice a Ice type so you can deal with Flying and Dragon, putting Dragon vs Dragon is not good.
Also a Dark type to deal with Ghosts and Psychic mons. A bug type would be nice too.
The best one in that regard is Weavile. Dark/Ice typing and if you spend a bit in breeding, it can have Throat Chop + Ice Punch.
As you need more special attackers, Houndoom would be very nice in place of Arcanine (as you suggested). Nasty Plot + Flamethrower/Dark Pulse are wrecking plus it has mega evolution (don't know if it's stone is available). Other option would be Delphox, still having fire type plus Psychic and great moveset.
If you do exchange Arcanine for Houndoom/Delphox, you could use Lucario with a Special Atk. set, giving you more coverage while still having a Fight type (now with STAB). Aura Sphere / Flash Cannon / Dragon Pulse / Shadow Ball / Psychic / Agility / Calm Mind. Plenty of options. Also has mega.
If you want, I can trade any of the mons I suggested 5ivs, proper nature and nice egg moves, all lvl 1. Hope I helped xD