[Alexandroppolus]

Навскидку видится такой вариант (сотворено на коленке, не дебажил):

function request(key, param, callback) { ... } // делает запрос в API

function APIClient(key, data) {
	this._key = key;
	this._data = data;
	this.nextTime = 0;
	this.loading = false;
	this._finish = this._finish.bind(this);
}

APIClient.prototype.start = function() {
	if (this._data.params.length) {
		var param = this._data.params.pop();
		request(this._key, param, this._finish);
		this._data.requests++;
		this.loading = true;
		this.param = param;
		this.nextTime = Date.now() + 1000; // следующий запрос через секунду, не ранее
	}
};
APIClient.prototype._finish = function(error) {
	if (error) {
		// запрос был с ошибкой, будем пробовать ещё раз для этого параметра
		this._data.params.push(this.param);
	}
	this.loading = false;
	this.param = null;
	this._data.requests--;
	if (!this._data.requests && !this._data.params.length && this._data.timer) {
		clearInterval(this._data.timer);
		this._data.timer = null;
		this._data.callback();
	}
};

function loadAll(keys, limit, params, callback) {
	var data = {
		params: params,
		requests: 0,
		timer: null,
		callback: callback
	};
	var clients = [];
	for (var i = 0; i < keys.length; ++i) {
		for (var j = 0; j < limit; ++j) {
			clients.push(new APIClient(keys[i], data));
		}
	}
	data.timer = setInterval(function () {
		var time = Date.now();
		for (var i = 0; i < clients.length; ++i) {
			var client = clients[i];
			if (time >= client.nextTime && !client.loading) {
				client.start();
			}
		}
	}, 300);
}

// запуск
loadAll([...], 8, [...], function() {
    ...
});

для каждого ключа создаем по 8 клиентов, все складываем в массив. Каждый клиент делает запрос не чаще раза в секунду. Отмечает время старта запроса (точнее, время следующего старта). И есть один общий таймер, который проверяет всех клиентов и стартует тех, которые уже успели "отдохнуть". Последний клиент, завершившись, уничтожает таймер и вызывает общий колбэк.

при такой схеме никто никого не ждет.

если требуется минутный интервал между финишем предыдущего запроса и стартом нового, то установку nextTime перенеси в _finish