Various locations, held by wild Paras and wild Parasect (50%), held by traded Nidoran♀FR/Nidoran♂LG
To get a Tiny Mushroom, you need to either catch or use Thief on a wild Paras or Parasect that is holding a Tiny Mushroom (There is a 50% chance for them to hold one.) Paras can be found in the Safari Zone and Mt. Moon, Parasect can be found in the Safari Zone and Cerulean Cave. Keep in mind that in order to successfully take a Pokemon's item with Thief, the user of Thief cannot be holding an item.
You can also trade a Nidoran♀ from another game to FR, but you cannot do this if you do not have two systems.
Minor edit: It appears that I misunderstood, the Tiny Mushroom is not held by a Nidoran♀ traded from another game to FireRed, it is held by a Nidoran♀ traded to you by an NPC at the Underground Path on Route 5.
Hope this helps!
Sources: This and this
