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>