NKVD
Cossack
Not having saltpeter was a pain but it wasn't a game breaker.because muskets (At Attack 2, Defense 4 were good on defense but weak on offense (Longbows had double their Attack but only 1/4 their Defense). If you could hang on until you had riflemen then you could still win. And if you didn't have rubber to build infantrymen you could still win by smothering their infantry with rifleman: the disparity between rifles and infantry didn't seem to be as great in III as it is in IV.
i dont know i never had games without it. i had always a big stack to get it right after its appearance. it was easier though with colonies...i dont know why there are no colonies in civ 4! those were fun and easy