I don't think you'll have any joy with anyone if you don't have a UK address. And I'm not positive, but I don't think you can open a store account without ordering something (or at least ordering a catalog - places like Next charge for their catalogs and then take that charge off of your first order).
You're going to struggle until you have an address and can open a bank account. Even then, it is likely to be just a really basic bank account which, after a year of making deposits, you can upgrade. I had my basic account for a year before they gave me an overdraft, but then they also gave me a credit card at the same time. And once you've got that far, it becomes far easier. Also, the bigger banks want three years of address history for credit cards.