You're on the right track with the base controller idea, but I would override OnActionExecuted and generate the data there. Check to see if the result is going to be a ViewResult before generating the common data. There's no need to generate the data if the result is a redirect or data going back via AJAX.
You might also consider creating a view-only model for the common data (if the data is extensive) and putting it in ViewData as a whole. Then you can create a strongly-typed partial view that takes the model and use the model's properties more easily in the view. Rendering this partial view from the master page would make it easy to both incorporate the data on every page and use it in a strongly-typed way.
If the footer data or formatting isn't complicated, then just putting the mark up in the master page is probably better.