Антон

В андроид локально хранить данные можно только в 3-х местах:
1. sdcard
2. внутренняя память
3. Защищённая (на нерутованных устройствах) область каждого приложения /data/data/ru.mycompany.myapp/

В первых 2-х лазить может любое приложение
В 3-ем только наше, но если телефон рутованый/либо лазит вирус - то тот, кто сможет получить доступ (через SuperSU либо exploit)

=> Остаётся хранить только как в /data/data/ru.mycompany.myapp/ плюс хранить не в чистом виде, а пошифровав сам ключ с помощью второго ключа (хоть xor-ом), который захардкоден в приложении.
Плюс в самом приложении вместо захардкоденного второго ключа ("ключа для ключа") - его можно динамически формировать по-частям, дабы не хранить целиком, иначе простым дизассемблированием можно его легко получить. Думаю этого должно хватить.

---
Если быть совсем параноиком - надо еще нереально заобфусцировать весь код превратив его в "big ball of mud" / встроить антиотладку (замерить время - и если превышает - идти на "обманную" ветку выполнения) - тогда уж точно мало кто захочет разбираться во всём этом...

---
Upd: Динамическая генерация мастер-ключа с обфускацией - даже дизассемблировав приложение, повозиться с такой головоломкой захочет не каждый...

public String getSomeKey1() {
    return "5";
}
public String getSomeKey2() {
    long key[32];

    key[0] = 9; 
    key[2] = 55; 
    a = (key[0] + key[2]) * 3; 
    key[1] = (a % 10) + someFunc() * 99; 
    key[4] = (a / 10) * someFunc2() / someFunc3(); 
    if (someFunc4()) { 
        key[5] = someFunc5(); 
    } else { 
        key[5] = someFunc6(); 
    }
    key[6] = Integer.valueOf(getSomeKey1());
    key = process1(key);
    key[2] = getSomeKey3();
    // ...
    StringBuilder sb = new StringBuilder();
    for (long i: key) {
        sb.append(i);
    }

    return sb.toString();
}
public long[] process1(long[] key) {
    key[3] = (key[4] + key[5] + key[1]*2) / 5;
    key[1] = getSomeKey();
    // ...
}
public long getSomeKey3() {
    long a = 435345435;
    boolean b = false;
    while (!b) {
        b = true;
        for (i=2; i<(long)Math.sqr(a); i++) {
            if (a % i == 0) { 
                b = false;
                break;
            }
        }
        a++:
    }
    return a+10;
}

// Итоговый мастер-ключ получаем так:
String masterKey = getSomeKey4() + getSomeKey2() + Integer.valueOf(getSomeKey1());