Template logic is primarily controlled by template-loader.php.
The part you are interested in would be get_404_template(), which passes on to generic get_query_template() with number of hooks to override the logic and result.
{$type}_template (so 404_template) filter would probably do it.