I know you find Terrakion on Victory Road but it seems like I've looked everywhere.
He is in the cave that is blocked by a small rock to remove this rock you must catch colbian in the mistralian cave.
At the very end of the cave there is a rock you can use strength on, push it out of the way, then proceed to his small cave ( nothing special ) and I would suggest saving before battling him, ( incase you kill him )
He's somewhere on victory road, but not quite sure where. I think I almost went to where he was at but I took a wrong turn and went straight to the E4. Although, like virizon in pinwheel forest you have to have either faught or caught coballion. The only path I didnt go on was the last split off before the exit at the end to the E4. Check there!