What's important in this scenario isn't whether there is air in the train or not, but whether the bullet (and, presumably, the gun that fires it) has any momentum before the gun is fired. The action of firing the gun exerts some impules $\Delta \vec p$ on the bullet, but its final momentum depends on its initial momentum.
For example, sometimes on long car rides my children think it's amusing to toss paper airplanes from the back seat to the front seat. On the ground, my children can toss paper airplanes at perhaps five miles per hour. If I'm on the highway, someone on the side of the road might measure a backseat-to-frontseat airplane as having a speed of seventy-five miles per hour. That's not an effect of the air in the car (and believe me, I've imagined removing all the air from my car on some of these trips); it's an effect of the initial momentum of the airplane.
You usually hear about this "puzzle" when one of the velocities is close to the speed of light.
For example, if $u$ is the speed of the car/train and $v$ is the speed of the paper airplane/bullet after it's thrown/fired, the observed speed after the toss/shot is
always given by relativistic velocity addition:
$$
\begin{align}
v' &= \frac{u + v}{1 + \frac{uv}{c^2}}
& &(\text{always})
\\
&\approx (u+v)\left(
1 - \frac{uv}{c^2} + \cdots
\right)
& &\left(\text{if } \frac{uv}{c^2} \ll 1\right)
\end{align}
$$
For a bullet (say, $v\sim 300\rm\,m/s$) on a train (maybe $u\sim30\rm\,m/s$)
the difference between the "right" way and the naïve way $v'=u+v$ starts
somewhere around the thirteenth decimal place, which is pretty deep in "don't care" territory: if the gun is the same, a bullet fired forwards from a moving gun will move faster than bullet fired from a stationary gun.
