onCreateOptionsMenu is never called

Call setHasOptionsMenu function from onCreate first. The onCreateOptionsMenu will be automatically called.

Try this:

setHasOptionsMenu(true)

In the latest versions of Android when using the compat library for toolbar, is very common that this happens, in order to get the menu items to display in the toolbar you must do the following:

mToolbar = (Toolbar) findViewById(R.id.toolbar);
setSupportActionBar(mToolbar);
getSupportActionBar().setDisplayShowTitleEnabled(false);

If the phone you test on has a menu button onCreateOptionsMenu wont't be called on start with the theme:

android:theme="@android:style/Theme.Black.NoTitleBar"

But when you click the menu button the onCreateOptionsMenu will be called. I don't know what happens on phones without hardware buttons...