Overriding UI designs can be such a pain. With Angular Material, I found that making a separate css file, often called override-material-ui, and using id selectors to change the styles instead of class names works pretty well. So for your code, it would be:
#override-toolbar {
background: red;
}
And the tag in the html would look like:
<md-toolbar id="override-toolbar">
</md-toolbar>
Obviously the toolbar tag would probably have more going on in it, but for override styles I find that this works best. It's nice when you have to style multiple tags the same way. Although inline effectively overrides everything, it can be annoying to change styles later on.
But, if even an ID selector won't cut it, and you don't want to deal with custom themes, go for the inline style selector.
Hope this helps!