this has nothing to do with Paypal, but I too am without a CC. Always had a bitch of a time figuring out how to order things online.
solution: Pre-Paid Visa/Mastercard, this are easy to find. Vons (Supermarket in So Cal) has em. You can add monies to it for 5 bucks. If I wanna buy something online that's 100 bucks, I go to Vons, give them 105 and I'm good to go. It works exactly as a Mastercard so there's never been any hastle.
I saw a pre-paid Visa @ 7-11's in Cali, not sure if this is a nationwide thing yet. But I believe they only charged 3 bucks to add funds to it.
Not as convient as a CC, but for us CC-less people, this is about the best option out there.