Free applications don't need a credit card stored in the Play Store to download. If you are wanting a paid application, then you need to use the available payment options.
I'm most definitely NOT a VZW employee. If a post answered your question, please mark it as the answer.
I think Sprint and AT&T are the only ones who offer the carrier billing for the Google Play store. Verizon doesn't as they would want a cut of that 99 cent app as they are money hungry people
Have you looked into PayPal? I thought I read somewhere that the Play Store now allows payments through PayPal.
After some digging, I see that you can pay using Google Wallet. Both of these solutions would allow you to not have you card number directly associated with your phone.
Also, even if you do use your card directly, you don't input it every time you install a paid application, in fact, you should be able to input it through the Play Store website (most likely through Google Wallet).