I have a header('HTTP/1.0 404 Not Found'); somewhere along the code but it doesn't redirect to the Apache's default 404 page for some reason.
I have a Rewrite Rule on the .htaccess file that redirects every request to index.php. Could that be the problem?
The header is not what tells Apache to display it's 404 page. Rather, when Apache displays its 404 page, it sends a 404 header along with it. The header is meant to have meaning to the browser, not the server. Apache displays a 404 when it can't find the proper file to display. Since you're in a PHP script, Apache has already found a file it can display, and thus won't show its own 404 page.
Headers sent by PHP only matter really to the browser in this case. Apache isn't going to make its own page because you are already processing the page, and if you sent something, the two would conflict.
Yes, the .htaccess file is going to stop Apache from showing an error page because your rules makes Apache think it no longer has a 404 error, because it has found a page to show.
Sending a header is really only a 'status message', and doesn't make the browser or server show a particular page. (Although most browsers will).
As Dav pointed out in the comments, you will want to send 404 errors to their own custom error page.
