Кластеризация - это не мой случай, так как при определенном зуме я просто не отображаю элементы.
Проблемы с лагами решила библиотека
Android Maps Extensions.
Видимо так оптимизировано отображение маркеров.
В связке с бибилиотекой я использую второй вариант действий из своего вопроса.