Where do new stars get their hydrogen from?

Stars only burn hydrogen in their core, where the temperature gets high enough for nuclear reactions to occur. They end their lives when they run out of fuel in the core, but lots of hydrogen still exists in their envelopes.

The Sun will burn 5-10% of its mass before exhausting its core. When this happens, the core will contract due to the radiation pressure disappearing. It then starts to burn hydrogen in a shell around the core. Eventually, when the Sun dies, it will have burned less than half of its hydrogen. Larger stars burn an even smaller fraction.

This means that, when stars die they still leave hydrogen behind for the next generation.

Galaxies can still run of of gas, though. Since after all, each $M_odot$ of star formed burns of the order of $1,M_odot$, if a galaxy isn't fueled with new gas it will become depleted on a timescale of order $1$ over its specific star formation rate sSFR, which is its star formation rate SFR measured in Solar masses per year, divided by its stellar mass $M_*$ in Solar masses:
$$
t_mathrm{depl} sim frac{1}{mathrm{sSFR}}=frac{M_*/M_odot}{mathrm{SFR}/M_odot,mathrm{yr}^{-1}}.
$$
For instance, a $10^9,M_odot$ galaxy with a star formation rate of $10,M_odot,mathrm{yr}^{-1}$ will become depleted of gas in roughly $10^8$ years.

Gas-depleted galaxies do exist, and the more depleted they are, the lower the star formation rate is (e.g. Rose et al. 2010), but in general the timescale is longer than the above, since galaxies also accrete gas from the surrounding circumgalactic medium.