It seems that Genesis has a built in 404 error message and not a 404.php page per say, so I have deactivated the redirection plugin, and implemented your option. It's a shame I can't combine the two into one ... missing links from store doesn't show up on the 404 error, and invalid urls that are non-store doesn't pick up the custom view page error message. I will think of something suitable and copy over to all my stores, but here is what I did so far...
e.g. if not a store product - the default Genesis 404 page (without a 404.php page)
One of the missing links mentioned from Google's crawl bot - Datafeedr Missing Product view
Originally Posted by Eric
I think a 404.php page would be very helpful and I'm surprised Studio Press themes don't ship with one. I would ask the SP guys how to implement a 404 page. That should take care of the issue.
However, if you want to display some specific store information on your 404 pages, you can create a new custom view in the Factory ( The Factory > Your Store > VIEWS > CUSTOM VIEW > Create a new view). Then name the view Missing Product. Then add whatever modules you want to the page. Now when product URLs result in 404s, this new Custom view named Missing Product will be displayed.