You can get Natu in the Ruins of Alph at Level 20 or Trade a Haunter for a Xatu in Pewter City.
Although, the Ruins of Alph location might be misleading. To actually get to the grass field where Natu is, you have to go to the basement of Union Cave, where there will be an entrance to the Ruins. :P
Source, 2
Hope I helped!