Magento Error 404 on every page

That is possible due to mod rewrite not working properly
To solve this check either mod_rewrite is enabled
if enabled then check your virtual host file and change it to following

Often virtualhost file contains AllowOverride none that actually restricts magento .htacess files to execute.
You need to put it to AllowOverride all.

Options Indexes FollowSymLinks MultiViews
AllowOverride all
Order allow,deny
allow from all