A toi de voir,
L'option KVM sur IP est dispo sur demande sur la Petite Dédibox, cela te permettra d'installer toi même l'OS de ton choix à partir d'une image ISO.
Après si tu préfère OVH, tu peux toujours te renseigner, d'après le site t'as un vKVM gratis et comme le dit Milk vois s'il ne propose pas une solution pour utiliser ta propre clé.
Et au passage, compare les 2 serveurs / hébergeurs voir lequel te conviens le mieux.