You are correct in your thinking that because the loop evaluates after the header you will not be able to get the contents of the loop there.
The easiest way to do this is probably with jQuery. Something like this:
<script type="text/javascript">
$(document).ready(function() {
document.title="blah";
});
</script>
Place this code in your loop, and the page title will be changed on after the document is ready. This may not be a desirable solution however, because some search engines do not evaluate JavaScript. You can use Google Webmaster Tools to see what the page looks like to the Google Crawler.
As an alternate solution, I believe All in One SEO Pack has the functionality that you describe:
- You can override any title and set any META description and any META keywords you want.
- Support for Custom Post Types
- Advanced Canonical URLs
- Fine tune Page Navigational Links
- Built-in API so other plugins/themes can access and extend functionality
- Support for CMS-style WordPress installations
- Automatically optimizes your titles for search engines
- Generates META tags automatically
- Avoids the typical duplicate content found on WordPress blogs
- For beginners, you don’t even have to look at the options, it works out-of-the-box. Just install.
- For advanced users, you can fine-tune everything