I know you can generate a one time use "credit card" number on your pay pal account. But, I don't know if you actually need a credit card tied to your account to do this. You may not. See if you can generate one of these CC numbers from PayPal without having a CC attached to your account.
If so, you should be able to use that at the store. The CC number can actually be used "more than once" as long as it is always used at the same vendor.