Presumably, the primary use case for this is to get a base model to the view for all (or the majority of) controller actions.
Given that, I've used a combination of several of these answers, primary piggy backing on Colin Bacon's answer.
It is correct that this is still controller logic because we are populating a viewmodel to return to a view.  Thus the correct place to put this is in the controller.
We want this to happen on all controllers because we use this for the layout page.  I am using it for partial views that are rendered in the layout page.
We also still want the added benefit of a strongly typed ViewModel
Thus, I have created a BaseViewModel and BaseController.  All ViewModels Controllers will inherit from BaseViewModel and BaseController respectively.
The code:
BaseController
public class BaseController : Controller
{
    protected override void OnActionExecuted(ActionExecutedContext filterContext)
    {
        base.OnActionExecuted(filterContext);
        var model = filterContext.Controller.ViewData.Model as BaseViewModel;
        model.AwesomeModelProperty = "Awesome Property Value";
        model.FooterModel = this.getFooterModel();
    }
    protected FooterModel getFooterModel()
    {
        FooterModel model = new FooterModel();
        model.FooterModelProperty = "OMG Becky!!! Another Awesome Property!";
    }
}
Note the use of OnActionExecuted as taken from this SO post
HomeController
public class HomeController : BaseController
{
    public ActionResult Index(string id)
    {
        HomeIndexModel model = new HomeIndexModel();
        // populate HomeIndexModel ...
        return View(model);
    }
}
BaseViewModel
public class BaseViewModel
{
    public string AwesomeModelProperty { get; set; }
    public FooterModel FooterModel { get; set; }
}
HomeViewModel
public class HomeIndexModel : BaseViewModel
{
    public string FirstName { get; set; }
    // other awesome properties
}
FooterModel
public class FooterModel
{
    public string FooterModelProperty { get; set; }
}
Layout.cshtml
@model WebSite.Models.BaseViewModel
<!DOCTYPE html>
<html>
<head>
    < ... meta tags and styles and whatnot ... >
</head>
<body>
    <header>
        @{ Html.RenderPartial("_Nav", Model.FooterModel.FooterModelProperty);}
    </header>
    <main>
        <div class="container">
            @RenderBody()
        </div>
        @{ Html.RenderPartial("_AnotherPartial", Model); }
        @{ Html.RenderPartial("_Contact"); }
    </main>
    <footer>
        @{ Html.RenderPartial("_Footer", Model.FooterModel); }
    </footer>
    < ... render scripts ... >
    @RenderSection("scripts", required: false)
</body>
</html>
_Nav.cshtml
@model string
<nav>
    <ul>
        <li>
            <a href="@Model" target="_blank">Mind Blown!</a>
        </li>
    </ul>
</nav>
Hopefully this helps.