Me ha costado encontrar cómo añadir margen entre el icono y el título en la Toolbar, así que lo posteo aquí, por si a alguien le interesa.
Si utilizamos la Toolbar que viene en la librería de Support, añadir un margen es tan fácil como añadir el atributo titleMarginStart.
A continuación un ejemplo de layout completo en el que aparece dicho atributo.
<android.support.design.widget.CoordinatorLayout
android:id="@+id/coordinator_layout"
android:background="?attr/colorPrimary"
android:fitsSystemWindows="false"
android:layout_width="match_parent"
android:layout_height="match_parent">
<FrameLayout
android:id="@+id/content"
app:layout_behavior="@string/appbar_scrolling_view_behavior"
android:layout_width="match_parent"
android:layout_height="match_parent" />
<android.support.design.widget.AppBarLayout
android:id="@+id/app_bar_layout"
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:theme="@style/AppTheme.AppBarOverlay"
app:popupTheme="@style/AppTheme.PopupOverlay">
<android.support.v7.widget.Toolbar
android:id="@+id/toolbar"
app:navigationIcon="@mipmap/ic_launcher"
app:title="@string/app_name"
app:titleMarginStart="32dp"
android:layout_height="wrap_content"
android:layout_width="match_parent"
android:minHeight="?attr/actionBarSize"
android:background="?attr/colorPrimaryDark"
app:layout_scrollFlags="scroll|enterAlways"/>
</android.support.design.widget.AppBarLayout>
</android.support.design.widget.CoordinatorLayout>