I have a website with mysql and php. I would like to try and use eXist-db instead of mysql. I believe I only have ftp access to that website (and a cPanel). Is there a way I can install eXist-db on the server? Or does it have to be done by the web-host directly?

Is that a Java program? You'll need to ask your webhost.

Some hosts can offer virtualization to let you install whatever you like, but that option often isn't terribly speedy...