1. Do not use VPS or Cloud hostings - only pure hardware.
VPS and Cloud hosts have several ways to get staff login to your server without a password and without rebooting server.
But even on pure hardware there is always a way to reset a root password when staff have access on console. Because of this:2. Keep your wallet on crypted partitions.
Use kernel-level partition encryption LUKS on Linux and ELI on FreeBSD.
When server crashed or rebooted, on next boot crypted partition can not be mounted without entering a password.
VPS and Clouds provide a theoretical fault-tolerance and safety of your data. So when you use a stand-alone server there is always small chance that HDD can be damaged causing loosing a wallet. So you need a backup to external host. If external backup host in a same DC, the chances of loosing both at ones - main and backup server - are high. So...3. Do not keep main bitcoind host and backup host in a same datacenter.
You also need to be sure your backups go through secure channel, So4. Use secure protocols to make an external backup. Such as SSH (scp).
Even if you backup your data via secure protocol, there always a chance that someone will get into the backup server and steal them. If you do not want to complicate the backup server setup:5. Encrypt backup files on creation with gpg-like standard unix utility. And then send them to backup host via secure channel.
This will let you use cheap untrusted VDS and Cloud services for backup purposes.
And finally, you have to restrict most ways to get your hosts to be compromised.6. There must be no applications running that listens network except bitcoind and sshd on main server, and sshd only on backup server.
PS. I don't say about complex passwords and pubkey ssh authorization, I assume people understand this. Also you may consider restrict ssh access by IP. But dont try too hard, you can restrict yourself