When you are using a custom Toolbar, you can use
toolbar = (Toolbar) findViewById(R.id.toolbar);
toolbar.setTitle(R.string.activity_title);
setSupportActionBar(toolbar);
getSupportActionBar().setLogo(R.drawable.logo);
and in your toolbar layout simply set app:titleMarginStart="16dp"
Note that you have to set the icon as a logo, don't use getSupportActionBar().setIcon(R.drawable.logo)
instead use:
getSupportActionBar().setLogo(R.drawable.logo)