Matheus,
A maneira mais prática é salvar esses tokens em Redis. Assim o tempo gasto para verificar a existência do token é praticamente insignificante, pois ocorre na memória, não no disco.
Não é necessário fazer duas requisições. Você irá usar um hash e alocará este no cabeçalho "Authorization".
Há bibliotecas prontas para isso, de forma que não é necessário fazer manualmente.
Um exemplo é a com.squareup.okhttp.Credentials.basic(String userName, String token). A string retornada é o hash no formato basic auth.
Como seu app não usa userName, pelo que entendi, este pode ser o nome da sua app mesmo (ou qq constante).
O importante é garantir que você é capaz de gerar uma chave de rápido acesso no servidor e o garantir que a app irá acoplá-la nas requisições.
O OAuth tb serve, mas é de implementação mais complexa. O basic auth, como o nome diz, é mais básico e atende seu caso.