Если "для нескольких пользователей", то ограничивать нужно каждый поток отдельно, ведь ограничение в 3 запроса накладывается на 1 токен.
Решение на php: пишем демона, который будет дергать запросы с базы данных (ну скорее всего в mysql) и выполнять их по очереди, соответственно удаляя из таблицы уже отработанные запросы. А ваши старые демоны будут складывать в базу данных эти запросы.
Если у вас небольшое приложение, то советую реализовать на nodejs, используя готовую либу vk-io
https://github.com/negezor/vk-io . В данной либе реализован сбор запросов в execute, как итог - мы можем делать 75 запросов в секунду с одного токена.