The reason why PHP redirection doesn’t work is, that because this part of code should be set on beggining of document, just before <!doctype>.Maybe you can do something like this:
Go into header.php, at the beggining of file add this:
<?php
if ( is_404() ) {
header("HTTP/1.1 301 Moved Permanently");
header("Location:http://www.exmaple.com/");
}
?>
EDIT: Sorry on wrong reply.