Какую БД использовать для деплоя телеграм бота?
На heroku есть нативный Postgres, есть бесплатная ограниченная версия. https://www.heroku.com/postgres
Если не слишком много данных планируешь хранить и кол-во запросов будет не большим, то можешь попробовать Google Firebase, там есть бесплатный тариф. 
Если, конечно, тебе не критично наличие именно SQL.