Skoorb, you could always try my approach - beat up (metaphorically) your bank manager. I spoke to my bank manager and he spoke to their CC issuing company who said if I could provide x information, they would be able to do it. I will be providing him with some paperwork and he will forward it to the CC company with the necessary information.
x = Proof of long term employment, proof of permanent residency, proof of income, and if I want to I can include credit history reports from home.
The most agravating part of this quest was when I rang the credit reference agencies early on. I explained my situation and asked them what I can do. Their answer - "Ask your bank for credit card, get a store card." and my response was - "but don't they come to you for a credit reference?"
Anyway, this was before I beat up the bank manager. When I first spoke to him he told me they couldn't help, but when I went back and discussed the issue at length with him he sorted me out.
BTW, do you use internet bill pay with your bank account?