Can't remove index.php without getting a 404, .htaccess redirect not working, why?
Check and make sure your .htaccess file is in your public HTML folder public/.htaccess!

If you do not include your .htaccess file in your public folder, Craft will display your home page properly, but all other pages will fail to load unless you add index.php?p= in your URL.

Without .htaccess:
http://website.com/mypagethatreallyexists = 404

Without .htaccess:
http://website.com/index.php?p=mypagethatreallyexists = Your page

With .htaccess:
http://website.com/mypagethatreallyexists = Your page