If installing Rails (or Flask, or whatever) isn't trivial compared to the difficulty of writing the actual code, then either your project is a toy, or your web host needs to get its act together.
It sounds like you've already lost.
In fact, I'll go so far as to say that what you're saying is indicative of the kind of out-of-touch response that keeps any of the proposed alternatives from replacing PHP.
Java, C and C++ are viable solutions, due to their popularity.