I live in the UK and pay for a US hosting service ( http://www.mediatemple.net/ ). Paying by Mastercard is pretty much the only way. Doesn't cost you any extra.
If all you want is the domain hosted, then I wouldn't say that you need much. Go for one of the cheapest as there won't be much of a quality issue involved.