You would have to write a server-side proxy that will do the pinging for you otherwise by the time you navigate to the URL it may be too late to know if it throws a 404.
Once you have your proxy script in place, call it via ajax supplying the URL your are about navigate to. If while trying to PING the URL it encounters error 404, then you can do your keyword search using your favorite search engine, otherwise navigate to the URL.
Please note: in case you want full control of the search results page, you may want to use the proxy to fetch the search results ..... and you'd kill two birds with one stone, just like that!