You can battle:
Your Rival. Ring him on the XTransciever to find out his location because they vary.
Cynthia. You will find here in Undella Town in the Villa nearest the Pokemon centre (Spring and Summer only)
Alder: You can battle him in his house in Flocessy Town
Black Tower: Unlocked after you beat Alder.
Benga (Alders Grandson): You can challenge him after getting to the top of the Battle Tower.
EDIT:
Colress: Go towards P2 Labortary (West of Nuvema Town) there you will see Team Plasmas Frigate. Go on that and head towards where you found Colress last time you were on the ship.
N: After beating the Elite Four take the stairs that are directly infront of the entrance to the Pokemon and you will notice there is a Zoroark there. Follow the Zoroark and it will take you to N.