Show block only on "Page Not Found"?
Can I recommend not doing it with PHP?

I would suggest making a page (via Admin->Content->Add Content), this assumes that you have the node module installed.

And then set that page as your "Default 404 (not found) page" in Admin->Configuration->System->Site Information

And then you can use that page's path in the block set up, but list under "Only the listed pages"