Думал сделать 4 колонки
Как раз 4 колонки тут и будут идеальным решением.
но из-за разного кол-ва блоков в колонках будут проблемы с адаптивностью
Не понятно, какие могут быть проблемы.
Flex сюда тоже так себе подходит
И флекс сюда подходит нормально. 4 колонки, внутри колонок flex-direction и всё встанет отлично.
CSS-Grid не предлагать ;)
Вот тут согласен, пока рановато его использовать.
https://jsfiddle.net/webirus/c0ktt24m/
В принципе, если высота известна, проблем вообще нет.
Если не известна, пару строк на JS, которые будут равнять блоки.
Ничего особенного нет.
Перестроение также легко делать через дополнительные классы в стиле bootstrap.
Аля column-xs, column-ls и так далее.