Are you looking at very cheap hosting or something which you can customise? If you don't mind paying maybe £15-20per month then a great solution would be a Virtual Private Hosting (VPS) server. That way you can install whatever you like on it without worrying about which hosting company you choose.
What I would also say is you're going to find it difficult to get a hosting company on a shared environment to give you that ability due to the resource overheads involved from their point of view so it might leave you with little choice!!