Ok, well I have finally gotten around to giving this a try.
Normal
Here I led with my Bulbasaur that had no item altering the encounter rate.
I encountered 124 Pokemon in 2000 patches of grass.
So I did some maths:
124/2000 x 100 = 6.2%
So the chance of encountering a wild Pokemon in normal conditions is 6.2%, which also means there is a 93.8% chance of encountering nothing.
Stench
Here I led with my Grimer with the ability Stench. My results really surprised me.
In 2000 patches of grass I encountered a total of 3 Pokemon. No, I am not joking/making this up. I seriously encountered only 3 Pokemon.
3/2000 x 100 = 0.15% chance of encountering something with a Stench Pokemon leading the party
Therefore a 99.85% chance of not encountering something.
Yes, with Grimer I think I just got very unlucky, but it still suggests that Stench does affect the encounter rate in FireRed/LeafGreen (I was using FR).
Also, something else I noticed. In the summary of Grimer it said that the abiliy Stench:
>Helps repel wild Pokemon
So that also suggests that Stench does indeed have the out of battle effect in FR/LG, even without my results.
Also, please note that it would be better if more people tried this, as one person can get skewed results, so my 6.2% chance of encountering something (for example) might be a little higher or lower than the true percentage, just through chance. This is the same for everything based on statistics.