Scaleway.com also offers baremetal servers at a really attractive price. The CLI is just awesome, it's great to see other cloud providers joining the game.
packet.net I do coreos and provision with userdata specifying what docker image to run... that's all it takes to have immutable deployment :)
Building a high-availability metadata store is not easy. And ensuring that incoming request IPs aren't spoof is a little non-trivial to reason about.
UserData is a good way to provide a one-time token that can be used to fetch data...
Using SSH for provisioning is just plain dirty... and almost impossible to do reliably... You'll need global locks and timeouts to recover in case one of your master crashes... Plus some garbage collection to cleanup things that where not fully provisioned.
This is a LOT of unreliable state to manage. And ton of corner cases. Having the right architecture matters for reliable automation.