How to detect if the referer is 404 page?

Easiest and most robust way is to add a url parameter to the search so the search url will be something like http://www.example.com/?s=xyz&from404=1. Probably easiest way to do that is by adding a hidden field to the form.

For “bonus points” use the browser’s history API to remove the parameter after the page load.