You can always upload your own, it's pretty simple doing so in a reproducible manner using something like Packer, but even without it you can just boot a VM into a rescue system, write your OS of choice to the VM disk and reboot.

Is it doable on a VPS? The documentation made it sound like it was for dedicated only. I went with OVH for this reason (which was cheaper anyway).

It is, yeah, the process is the same: boot into a rescue system running in memory, and do whatever you want with the disk.