А что мешает поместить навигацию, логотип и т.д. внутри дива с градиентным бэкграундом?
<header>
<div class="bg_header">
<nav>
<ul>
<li><a href="#">Пункт1</a></li>
<li><a href="#">Пункт2</a></li>
<li><a href="#">Пункт3</a></li>
<li><a href="#">Пункт4</a></li>
<li><a href="#">Пункт5</a></li>
</ul>
</nav>
</div>
</header>
header - задаете бэкграунд картинкой
.bg_header - задаете бэкграунд градиент и не забываете указать ему высоту во весь хедер.
nav - остается поверх и картинки и бэкграунда.
Вот как-то так:
codepen.io/anon/pen/bwNmvr 
