I've been thinking about this and I like the idea of building the software to run on Heroku (or similar). For those that want a self hosted plan you just tell them where to host it and if they want installation outside of that you charge them a decent hourly rate to make it worth it.