Recently, CoinStar started a campaign where they won't charge you any fee if you turn your coins into iTunes gift cards, Amazon gift cards, or Virgin mobile cards. The machine doesn't actually give you any cards, but rather PINs which can be typed in on the sponsor's site and redeemed for their value. This works because the CoinStar machine has the power of the internets.
How to do it
This is really quite simple. Follow the directions as usual, but when it asks how you would like your money, make sure to pick the iTunes gift card. After it counts all of your change, the machine will ask you how much of your money you want as a gift card and how much you want as cash. Go ahead and set it all to gift card. Now, before proceeding, you need to find a way to unplug the phone jack from the back of the machine. I'm lucky because the wall phone jack for my local CoinStar is at about shoulder height right next to the machine.
Now the poor machine is in quite a pickle. It already has all of your change, and it can't give that back to you. It can't give you an iTunes card either. It could give you cash, but it's not going to lay that 9% fee on because you obviously didn't agree to that when you put your change in the machine. What can it do? Give you cash for FREE. After a few minutes of trying, it will simply give up and just give you a slip which can be redeemed for cash at the store customer service counter.