I got my Korean Credit card but the only bank that would issue me one was Korea Exchange Bank, which is not bad since they have the best foreigner service and great online banking. But I had to prove that I had been resident in Korea for more than a year, that I was employed here and I had to give 3 month's bank statements proving income. They did not require a deposit but you cannot pay the balance partially in a month, it has to be paid in full. Which of course is ideal for when you want to use it to accrue miles.

I personally went with the Crossmiles Credit Card. It is indirectly affiliated to either Korean or Asiana (you choose upon signing up) but it earns what is known as "crossmiles." You earn 1.8 crossmiles for each W1500 spent. At 5000 crossmiles you can covert it to a number of programs including Asiana/Korean depending on what you chose at a 1.5:1 ratio or Delta at a 1:1 ratio (and some others which might be less relevant to the people on this forum.)

Additionally it gives lots of benefits like some lounge access at Incheon, monthly free brunch at Starbucks, free coffee at the airport etc.