After entering the Hall of Fame for the first time, go back to Victory Road. I suggest you start from the top. Look for a Zoroark.
It will be standing outside in the grass, like a trainer waiting to battle you. Get close and it will run away. Follow it. It will take you to the ruins of N's Castle under Victory Road.
There, you will find N.
(Note: You cannot catch this Zoroark.)
Source: Done it before. If you need help, find a video on YouTube. I cannot access YouTube at this time.