A 7.5¢ coin would solve this, right? Coke actually lobbied the Treasury to produce one, but they understandably refused. So if you still want to take a single coin, and your small coins are limited to 1¢, 5¢, and 10¢, what can you do?

Coke explored the idea of probabilistic pricing, where your nickle usually gets you a bottle but doesn't always:

Instead of offering one Coke for 6¢ the coin cooler offers eight Cokes for 45¢, which is only 5.625¢ per bottle. [The] coin cooler [delivers] either an empty bottle or no bottle at all for one nickel in every nine deposited. This absence of Coke is called an official blank. Please be warned that, if you fail to deposit nine nickels, at worst you will strike the blank and have to deposit another nickel for your Coke. At best you will miss the blank (8 times out of 9) and your Coke will cost only a nickel, but as stated, on the average Coke sells for 5.625¢ per bottle—the only price at which it is offered.

• —Eugene Kelly, Single Coin Plan, 1951, Coca-Cola Company Archives. Quoted in Levy and Young 2004.

The main problem with this is that you set people up to be disappointed. Usually their 5¢ gets them a bottle, but sometimes it gets them nothing. Greedy vendor! So here's an alternate approach: require dimes [1], but return the coin 44% of the time (giving them their bottle for free). It's the same 5.6¢ cost, but now you've set up people for a positive surprise instead of a negative one.

There are still other problems with this probabilistic approach to change-making, including that you're stepping a bit close to gambling and slot machines, but I'm curious whether their Single Coin Plan would have gotten farther with test audiences as "sometimes you get a free Coke" than "sometimes you get no Coke".

(For more history of how and why Coke kept their bottles at 5¢ for over 60 years, see Levy and Young's 2004 "The Real Thing": Nominal Price Rigidity of the Nickel Coke, 1886-1959.)

[1] This does mean you have to update your vending machines to take dimes, but they were willing to do that for a new 7.5¢ coin so it seems like they they would have been ok doing that here.