Well, first of all, the guy that teaches you moves that your pokemon has already learned but you got rid of, is onn one of the first four islands. (I just did this last night... No idea how I forgot...) He asks for either two Tiny Mushrooms, or one Big Mushroom. These are both items that can only be found randomly on Paras and Parasect. Well most people would think, "Hey, I'll just go to the safari zone and catch a Parasect and get a Big Mushroom." Well, it's not that easy. Since your in the safari zone, it's never a sure thing if you'll catch the Parasect, so here's what I did.
Your going to need Surf for this. Fly to Cerulean City and bring Ultra Balls. (Ultra Balls because the Paras will only be around level 10, so you can catch it without weakening it.) Then go up the Nugget Bridge and Surf downwards as if you were going to Cerulean Cave. From here you can hop ledges and get back to Mt. Moon. Once you see the cave and walk in, you only need to stay in that area. You don't need to go any deeper into the cave. The Paras here are VERY easy to catch. Now something I noticed for myself, is the ones with the mushrooms, took two or three Ultra Balls then ones that didn't. When I did this, I caught four Paras. Three out of the four held a Tiny Mushroom. That's a 75% chance that you will get a Tiny Mushroom from them, or at least in my experience.
Well, I hoped this helped at least one person, because I thought it was ALOT easier then trying to catch Parasect in the Safari Zone.