For a VPN that you connect to directly, it doesn't matter very much. An adversary that has tracked you back through the VPN knows your IP address. If there's a credible investigation, your ISP will provide your identity. Paying anonymously for a direct-connect VPN would at best stop an adversary that couldn't gain the cooperation of your ISP.
I've written a guide on paying anonymously with cash and Bitcoins. One option, as Roya has mentioned, is paying with cash by mail. I address concerns about serial numbers, printer fingerprints, hindering DNA analysis, avoiding surveillance and so on, and offer suggestions based on my experience.
I cover using Bitcoins anonymously in great detail. I recommend multiple transfers through mixing services, using MultiBit clients in multiple Whonix instances. For better anonymity, each Multibit client should have a wallet with several sending and receiving addresses, or even several wallets. For each transfer from one client to another through a mixing service, you randomly spread the Bitcoins among several address combinations. That increases the anonymity that each transfer provides, by reducing correlation based on quantities transferred.
Reputable mixing services include BitLaundry, Blockchain (sending via “shared wallet”), and Bitcoin Fog. Avoid OnionBC. It has either broken, or become a scam. It accepts deposits, but won’t execute withdrawals.
After each mixing step, it’s crucial to check receiving addresses for taint from sending addresses. On the Blockchain explorer page, enter each receiving address in the “Search” field, and hit enter. Then click “Taint Analysis”, and download the results. Once you have all of the data, search the taint results for each receiving address for the corresponding sending address. If it appears, you need to remix that component.