Many web design companies start of with a VPS (about £30 a month) and once you get enough clients you could move up to a dedicated server
I’m not sure how much flexibility you get with a VPS in terms of shell access etc, so you may want to look at cloud hosting providers as that way your client is billed for what they use.
Check out this mega-thread for options:
You may also want to look at Gigalixir: Platform-as-a-Service designed just for Elixir/Phoenix (they also have a free option).