Although there's a lot that you can do to protect your box, but I do believe it is very hard to make sure this doesn't happen again if the server is not managed properly.
Well, with your root password being changed, literally your server is owned and it becomes a shared entity between you and the hacker which is a no no for sysadmins.
On regaining access to your server for a linux box(yours should be either a vps, dedicated server or your own server colocated at the hosting provider, but I may be wrong), I do believe that the usual answer is ssh? If you cannot access the ssh server with your credentials, then you may need to contact your hosting provider to help you on it.
After that, you need to find out the entry point on how the hacker penetrated your server(which is where the vulnerability lies).
Places to look at:
- Vulnerability at the server side scripting code (php, asp, aspx, jsp, cfm and etc)
- Vulnerability at the processes that your server is running(apache, ftp, mail server, ssh)
- Etc(not listed as it is too broad)
Howto deal with it:
- Trace your server logs for any signs of hacking incident(if the hacker has already removed the logs then you're out of luck that you may need to check the codes on your own) and patch the vulnerability.
- You can do a check up the here for any 0day vulnerability by typing the name of the software and the version of it and wait for the vendor to patch it up or you can patch it yourself(if you know how to).
- Etc(not covered as there are too many solutions for different set of problems)
If you managed to retrieve a backup from your hosting provider during the hacking incident, it is advised that you don't restore it and use it as it is(just retrieve the content) as a shell may be embedded into your code and the hacker can just access it and hack it again.
Next time, disable the processes that you don't need(i.e mail server, ldap, or ftp if you don't send emails or you use a webbased service to upload your files) as it increases the possibility of being hacked(more attack vectors can be tried upon your server) or limit it to only your IP(get yourself a static IP in which you achieve through a few methods).
Whether to nuke your server or not, its your call although I do recommend you to nuke it.