Create second custom 404 page for selected post type

Two options:

  1. Use conditional code inside of 404.php, to output different content/markup for the post-type
  2. Intercept the template at template_redirect, and include a separate template file for a 404 for the post-type.

Personally, I’d go with option 1, as it is easier and more intuitive.