A) Yes, it would fire. Gunpowder--like most explosives and conflagrants--is composed of many compounds, including nitrates. The nitrate ion, NO3 (-1) carries three oxygen atoms to donate to the combustion reaction. It's not the oxygen gas inside the casing--the gaseous contents are truly trivial in the scope of things--but rather the oxygen stored chemically in the compounds (called "oxidizers" for a reason).
B) Ignoring the question of how we define "stop" (what's our frame of reference--Special relativity says there's no such thing as an absolute reference frame, so you can't say "it's not moving" as an absolute, just "not moving relative to x"), the bullet would ultimately end up in the sun if it didn't achieve Solar escape velocity (discussed above). The bullet would orbit the sun for a long time, but it would lose a minuscule (barely measurable) amount of energy each time it collided with a stray hydrogen molecule. Each collision would cause a degradation in the bullet's orbit (again, barely measurable, if at all), but the cumulative effect over an unknown period of time (decades? Centuries? Millenia? Longer?) would ultimately result in the orbit collapsing into the sun--unless, of course, the bullet collided with another body first.
If somehow the bullet did achieve escape velocity, it would continue into deep space, again being minutely deflected by each collision with a random atom or molecule. Ultimately, it would be captured by another body's gravity (based on the fact that space has a nearly-limitless number of stars, probability suggests that gravitational capture would happen eventually), resulting in the same scenario as in our own system, just a whole lot later.
Of course, during the countless aeons, the metal of the bullet would sublimate from the surface. It happens here on Earth, too, but what's a few thousand atoms per year? De nada, until you start talking millions or billions of years. If somehow the shot managed to avoid gravitational capture long enough, it might just evaporate into the imperfect vacuum of space, becoming one of those "several atoms per cubic meter."
How long do you want to wait for an answer?