That is very weird!
First, try going into Settings > Permalinks. (When you LOAD this page, it rebuilds the permalink settings.) See if that fixes it, by chance.
Now, try changing back to Default permalinks (no URL rewriting happens here). Can you see the same pages this way? (Of course, you cannot call them with those URLs - none will work. But you could try clicking on the page links below, which should adjust to the default URL structure.)
I assume that this last technique will give you no 404s. But at least it gives you a tiny bit more data. Then, change the Permalinks back to the way they were.
Now, since this is a weird situation, I would try disabling all the plugins, and see if the problem is still there. If it is fixed, then, go to Recently Active plugins, and turn them back on one by one. You will find the plugin that is causing some problem (who knows why?). If not, then that is not the issue.
You could also look at the error logs for the site (from your hosting control panel, often), to see if you are getting an error and what kind, with the 404.
Now, you get into weirdness of rewrite rules—maybe *something* is weird. You could try using http://wordpress.org/extend/plugins/rewrite-rules-inspector/ ... this gets pretty advanced, so it might be too advanced to do alone, but it makes it less difficult to understand.