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);