Astronauts in the ISS only feel like they are in zero-g because they are falling at the same speed as the ISS is. But they are still feeling the effects of gravity.
Would the same happen if suddenly there was NO gravity? Like, they were put in some region of space between two galaxies? (I know there will always be some gravity, but it is so small that it wouldn't matter)
Well, in Newtonian Physics and Special Relativity, Gravity is a force (although special relativity doesn't really deal much with gravity at all, it basically makes the same assumptions about it as Newtonian physics does, and it's the fact that those assumptions don't work well in special relativity that lead Einstein to go one step further and develop General Relativity).
In General Relativity, gravity and the law of inertia are exactly the same thing. An object at rest will remain at rest unless acted upon by an outside force, and an object in motion will remain in motion unless acted upon by an outside force, but space itself moves inwards towards massive objects, so that "remaining at rest" or "in motion" becomes "falling". Black holes are unescapable because space at the event horizon is moving inwards at the speed of light (and faster inside), so that an object would have to move faster than the speed of light just to be able to move outwards. (This explanation is a bit rough, but is probably the best I can do without an in-depth course on what exactly "spacetime" means, and what it means for it to be curved, and how exactly special relativity works, etc, etc).
In any case, General relativity states that, with regards to the forces you feel, there is no difference at all* between being in freefall in a gravitational field and sitting still (or maintaining a constant velocity) outside of one. It also states that there is no difference at all between the forces you feel when standing on a planet with a one-gee surface gravity, and those you feel when accelerating in a rocket at one g.
(* This is not completely true. In the vicinity of a planet, you will feel tidal forces due to the difference between the effects of gravity at different points, and the fact that you yourself are not just one point, but if you're really small, or the planet is really far away, you won't feel them as strongly. If you were so small that you were just one point, then the statement in question would be completely true.