Думаю, для ваших целей вполне хватит хранения данных о текущем (онлайн/оффлайн) состоянии в оперативной памяти, выделенной приложению. Т.е. тупо в коде.
Другое дело - хранение данных о том, какие id из vk вообще отслеживаем - найдите самое простое решение на вашем языке и заюзайте его.
Код тг-бота будет простым. Логика там такая: каждый написавший боту, с точки зрения кода, это "диалог", у которого есть уникальный id.
У бота есть метод .send(id диалога, текст сообщения).
Рассылка делается циклом по списку диалогов - его можно фетчить из tg каждый раз, можно где-то хранить.