First stop would be your own bank, no doubt they offer a card. Expect to be knocked back first time, but try again, and again.
Credit cards have an issue where you can load them up, then disappear into the mist. For a foreigner, thats dead simple - leave Japan, and being a flight-risk means banks will be wary of giving you a card. Its a fair point, how much money would you loan to a foreigner stranger?
The longer you have been here, the longer you have work, being married, having children, owning your home rather than renting will all be factors that work for you, and its all questions asked on the application form.
One of the easiest ways to get a card is from a department store, who are more than happy to give it to you. The features and benefits are not as good as a bank-based card would be, but they generally offer 2 months no-interest, no fees (barring a yearly ~1000yen fee), and it has all the "features" a normal visa card would, meaning you can use it online, in stores, etc. I'm sure if you ask nicely they might even do cash advance.
Funny story - when I opened a Citibank account here in Japan I was offered a visa card, but refused because I wanted a debit card, and was told that I could not get a debit card (which to me is low-risk for them) until I had held an account for 6months. After 6 months my own credit card from Australia had expired, so I figured I would get a Citibank card, and they refused several times over the following year. Wonderful eh?