In the .htaccess which can be found in the root of your WordPress installation add the following code:
ErrorDocument 404 /[pathtopage]/[page]
Replace [pathtopage] and [page] entries with real values, i.e. the new 404 error page you will be using.
Basically you are instructing your web server that each time someone requests a non existing URL, instead of forwarding him or her to the default 404 error page, the user is redirected to the newly specified 404 page.
If you do not see .htaccess file via FTP, make sure your FTP client is configured to show hidden files. If there isn't any, create a new one.