set_error_handler() doesn't work for FATAL error

Simple Answer: You can't. See the manual:

The following error types cannot be handled with a user defined function: E_ERROR, E_PARSE, E_CORE_ERROR, E_CORE_WARNING, E_COMPILE_ERROR, E_COMPILE_WARNING, and most of E_STRICT raised in the file where set_error_handler() is called.

For every other error, you can use set_error_handler()

EDIT:

Since it seems, that there are some discussions on this topic, with regards to using register_shutdown_function, we should take a look at the definition of handling: To me, handling an error means catching the error and reacting in a way that is "nice" for the user and the underlying data (databases, files, web services, etc.).

Using register_shutdown_function you cannot handle an error from within the code where it was called, meaning the code would still stop working at the point where the error occurs. You can, however, present the user with an error message instead of a white page, but you cannot, for example, roll back anything that your code did prior to failing.

This works for me:

function shutdown() {
    $error = error_get_last();
    if ($error['type'] === E_ERROR) {
        // fatal error has occured
    }
}

register_shutdown_function('shutdown');

spl_autoload_register('foo'); 
// throws a LogicException which is not caught, so triggers a E_ERROR

However, you probably know it already, but just to make sure: you can't recover from a E_ERROR in any way.

As for the backtrace, you can't... :( In most cases of a fatal error, especially Undefined function errors, you don't really need it. Pinpointing the file/line where it occured is enough. The backtrace is irrelevant in that case.