При отправке любого сообщения можно обновить клавиатуру.
bot = telebot.TeleBot(token)
keyboard = types.ReplyKeyboardMarkup()
bot.send_message(message.chat.id, 'Сообщение', reply_markup=keyboard)
Остается отправить всем пользователям сообщение с новой клавиатурой. Например, собрать все chat_id текущих пользователей в список users_list и:
@bot.message_handler(commands=["new_keyboard_for_all_users"])
def send_new_keyboard (message):
keyboard = types.ReplyKeyboardMarkup() # Новая клавиатура
for user in users_list:
bot.send_message(user, 'Произвольное сообщение', reply_markup=keyboard)