You should be able to adjust the error.php file 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);