I'd also suggest to focus on niche. One particular niche that I can probably think of right now is "pay as you go" or "prepaid" hosting which is only provided by nearlyfreespeech.net as of yet.

I think you can experiment with billing and can come up with an innovative sales pitch. Also honesty matters a lot in this industry. It's the reason why people who host on nearlyfreespeech.net, prgmr.com and linode.com swear by their service.