There's a simpler option for the lazy ones out there.
TL;DR: Just create a new style with the colorPrimary being your desired color and then set the NavigationView's theme to be this new style.
Just make a new style as:
<style name="AppTheme.NoActionBar.NavigationView">
<item name="colorPrimary">@color/myDesiredColor</item>
</style>
This style will automatically inherit from your base theme (on my case it was AppTheme.NoActionBar) and then you just have to set the colorPrimary with your desired color.
Then you just have to set the NavigationView's theme as:
android:theme="@style/AppTheme.NoActionBar.NavigationView"
in:
<android.support.design.widget.NavigationView
android:id="@+id/nav_view"
android:layout_width="wrap_content"
android:layout_height="match_parent"
android:layout_gravity="start"
android:fitsSystemWindows="true"
app:headerLayout="@layout/nav_header_menu_test"
app:menu="@menu/main_drawer"
android:theme="@style/AppTheme.NoActionBar.NavigationView" />