I think the recent outbreak of measles in the state of Washington can help answer this question. Opposition to vaccination does not fall neatly along political lines in the US. From my own anecdotal observations self described liberals appear to hold the plurality among so called "anti vaxxers" but there are plenty of conservatives, libertarians, and other political ideologies who hold this view as well.
Washington, for whatever reason, seems to have a larger than usual population of anti vaxxers especially in the Seattle area. As the news coverage of the measle outbreak increased, there was a corresponding increase in demand for measle vaccinations. It seems the fear of contracting measles began to win out over the fear of vaccination. So in this sense the problem is self correcting. There are, of course, non-coercive means of encouraging vaccination.
@xirath alluded to one most libertarians advocate, social ostracism. Most schools and colleges already employ this in the interest of their students. Few colleges will allow admission of a student without proof of vaccination. I recall being required to get an MMR booster when I re-enrolled in college about 12 years ago after an extended absence. It turned out my initial vaccination schedule was given under the guidelines of another state and the college refused to allow me to attend unless I had another shot. They did offer an exemption on religious grounds but my religion did not prohibit vaccination and I saw no reason not to get it again.
Another potential solution is economic self interest. An insurer might charge a higher premium or exclude coverage for treatment to clients who forgo vaccinations. A change in tort law could open the door for restitution if a plaintiff could provide evidence that they contracted a disease as a result of a defendant's refusal to be vaccinated. Though that may be hard to prove. Those are just two other possible solutions.
I'd like to focus on one of your assertions in the question for a moment.
But if enough people choose not to be vaccinated, then that impinges
on those who can't, but want to be protected.
This isn't a foregone conclusion. An unvaccinated person is not a sick person. It only increases their chances of contracting a disease. Judging by the number of cases of measles being reported and given that the measles vaccine lasts a very long time it seems a significant portion of the population had been avoiding vaccination for some time without major incident.