Treacle, you say the main page is different every time. That's not really relevant. The "main page" (I assume you mean the home page) is not the one that will attract your audience.
It's the pages that contain your actual content that people will be searching for, and which will show up in search engines. It is those pages that you need to worry about, from an SEO point of view. A home page that shows random entries each time might be useful for casual browsers, but it's not relevant for SEO.
By the way, rather than showing random entries, have you considered having the main page show the most recent content, or perhaps the most popular? That might be something your regular visitors will appreciate (but, again, it's got nothing to do with SEO).