So, I hopped on my Nintendo DS and put in Pearl (NOT stolen from my sister :D) And had a look for Pokemon around the area you're up to. Here's what I found, the pickings were pretty slim. SPOILER:
Shinx: Yes
Budew: Roserade is good.
Misdreavus: I found this in Eterna Forest at nighttime. Currently using one in Pokemon Colosseum nicknamed
Daria, I like her :) You can evolve her into Mismagius, since this is 4th gen.
Chimchar: Keep him for now at least, I don't like the design but at least you'll sweep Gardenia easy. Also, a fighting type move might help you with more coverage later.
Bidoof: Useful for HM slaving. You want him, don't deny ;)
Others found: Wurmple, Silcoon, Dustox, Machop, Gastly, Cleffa (could replace Misdreavus but needs trade to evolve to Gengar), Meditite, Ponyta (could replace Chimchar), Buneary, Chingling! (found at night, not strong but I love Chimecho <3)