Multiple 404.php templates based on a post_type

It is possible but wordpress doesn’t have any helpful constructs to help with that.

The best approach is to modify your 404.php. Most of the information that you need should be in the main WP_query object and you should be able to do something like

if (is_singular('post_tyoe_a')) {
   ....
} else {
   ....
}

this is extremely untested and you might need to just try to see if enough information is included in the query to do what you want, but if not you can always just check if the URL matches the prefix used for the permalinks of your CPT.