If you can't get a "real" credit card, I would advise you to get a debit card tied to a checking account (these are very common in the US and Canada) - these look and function exactly as a credit card, but actually don't provide you with any credit (so you don't need credit approval), they're tied to your actual account balance. So you will get all the functionality of a prepaid card without the inconvenience and the extra fees.
If you're using this for travel, make sure there are no big foreign transaction fees and no big foreign ATM cash withdrawal fees. Shop around, it's possible to find a good deal. I have a card like this from a small credit union in the US, not a major bank, which only charges 1% for ATM withdrawals - I've successfully used this card in Russia.
Another way to break out of the "can't get a card because no credit - no credit because no card loop" is to get a "secured card", some banks allow that (e.g. you give the bank $500 to store in an interest-bearing account for you which you don't have access to, they give you a card with a $500 credit limit). Of course, you can get your money back if you cancel the card, and the advantage is that it starts building your credit history.
By the way, if you're taking cash to Russia, beware of a common foreign exchange scam where the exchange rate you see posted is actually an exchange rate for large sums of money (as indicated in Russian fine print :), and the actual exchange rate for typical traveler amounts is much worse. Always have them show you on a calculator how many rubles you're getting before physically handing over your cash.