An small EC2 instance will run you $70 a month, plus assorted bandwidth and storage fees. They've got a Europe availability zone, but not specifically UK. Very low level access, but up time is best effort, which in reality is all any other cheap hosting provider is. (EG: I don't want my $.10 for the hour back)

Matthew