Please see information that I was able to get regarding the elusive Fireman zombie (Courtesy of TotallySteve) :
1. Wifi connection - do you need this or if you already have the updated game, you will just see it.
Answer: If the update with the Fireman has been installed, playing online isn't necessary.
2. OS - haven't seen it in 4.0.4 ICS or 2.2 Froyo
Answer: Seems like a coincidence.
3. What are the chances of seeing a Fireman zombie? Are we looking at maybe 10% chance of appearing?
Answer: I can't speak to the exact percentages, but it's probably a little bit less than 10%.
4. If you have already finished all the story missions, will you still be able to see the fireman zombie?
Answer: This shouldn't matter.
From what I've been told, the Fireman is just a random zombie. He's considered "Uncommon," so he won't show up in an special way; players will see him in the randomly-generated hordes.
Comments and questions welcome.
The Wolf Pack are my friends, like all others whom I have the pleasure to know. You have my respect because you deserve it - the same way I expect this respect from you as well.