You should be able to adjust the error.php to set the header either with the
1. Joomla way:
$app = JFactory::getApplication();
$app->setHeader('HTTP/1.1', '404 Not Found',true);
$app->sendHeaders();
2. PHP way
header('HTTP/1.1 404 Not Found', true, 404);