What's best practice for using a completely custom navigation/header? Is it to create a visualforce tab and place it next to the home tab, and then have that be the landing page for the salesforce app? Or is there a better way to override the actual salesforce home page with a custom header?
That is what I did. It works well, but there are some holes. Like if you have the option for the user to navigate to their profile, they get the standard Salesforce header. I saw a post one time saying that there was some HTML you could put in the home page in a custom component that would redirect a user that landed on the home page, but I couldn't get it to work. Salesforce, as far as I know, prevents you from removing the home tab.
I have been using custom skuid headers and footers for months in two orgs and it works great. If you remove any options from your navigation components that would navigate users to a page that only works with Saleaforce headers, then it should do the trick.
If you want to keep some of the standard salesforce pages that deliver good value (like profile) you can add custom links to your navigation and include the url parameter "&isdtp=vw" to the end. So this