**Solventado**, cogiendo ideas de las respuestas:

    private int getFirstTimeRun() {
        SharedPreferences sp = getSharedPreferences("MYAPP", 0);
        int result, currentVersionCode = BuildConfig.VERSION_CODE;
        int lastVersionCode = sp.getInt("FIRSTTIMERUN", -1);
        if (lastVersionCode == -1) result = 0; else
            result = (lastVersionCode == currentVersionCode) ? 1 : 2;
        sp.edit().putInt("FIRSTTIMERUN", currentVersionCode).apply();
        return result;
    }

Los valores que devuelve la función:

 - 0: la App no se ha ejecutado nunca.
 - 1: la App alguna vez se ha ejecutado.
 - 2: la App se ha ejecutado alguna vez, pero no esa versión.

**Ejemplo de uso:**

    switch(getFirstTimeRun()) {
        case 0:
            Log.d("appPreferences", "Es la primera vez!");
            break;
        case 1:
            Log.d("appPreferences", "ya has iniciado la app alguna vez");
            break;
        case 2:
            Log.d("appPreferences", "es una versión nueva");
    }

Se acepta mejoras de funcionalidad y optimización de código.

**EDITADO**

Otra manera es usar la librería [Once][1] :

Inicializar con: `Once.initialise(this);`

**Métodos primera vez:**

La primera vez que el usuario instala la app:


    if (!Once.beenDone(Once.THIS_APP_INSTALL, "tag")) {
        //Primera vez que se instala la app
        Once.markDone("tag");
    }

La primera vez despues de upgrade de la app:


    if (!Once.beenDone(Once.THIS_APP_VERSION, "tag")) {
        //Primera vez despues de actualizar la app
        Once.markDone("tag");
    }


  [1]: https://github.com/jonfinerty/Once