Se tu perdeu a keystore da Play, infelizmente, já era. 😢 

Não existe uma maneira de recuperar, inclusive, este é um cuidado que sempre devemos ter (fazer backup da chave). Por conta disso, eu geralmente prefiro gerenciar a chave manualmente (ao invés de deixar o Google fazer isso) e assim que crio o projeto, já faço bkp da chave.

Pior que realmente era a keystore, não pensei em fazer um backup quando publiquei o app, depois formatei meu pc, aí percebi que não tinha salvado a chave

Se tu tinha a chave na pasta do teu projeto, antes de formatar teu PC, talvez valha a pena tentar recuperar o arquivo, com um programa tipo o Recuva..

Se tu perdeu a keystore da Play, infelizmente, já era. 😢 Não existe uma maneira de recuperar, inclusive, este é um cuidado que sempre devemos ter (fazer backup da chave). Por conta disso...