Redirect to 404.php from single.php

Try something like this:

header("HTTP/1.0 404 Not Found");
$wp_query->set_404(); //This will inform WordPress you have a 404 - not absolutely necessary here, but for reference only.
require '/path/to/404.php';
exit;

Just do the error handling on the page itself instead of redirecting it to another template. This will maintain your 404 header and give you complete control right within the parent template.