OVH has FreeBSD templates. And most KVM VM/VPS providers will allow console access and mount custom ISO to install whatever you want.