промисы же сами по себе асинхронны
Это ваша принципиальная ошибка. Не асинхронны они. Promise исполняет переданную ему функцию немедленно. Вот внутри переданной функции можно делать что-то асинхронное.
А можно не делать - как у вас в первом случае. Получается так - промис создаётся, тут же происходит resolve, дальше в цикле создаётся следующий промис, который в свою очередь тоже немедленно резолвится и так далее. В результате у браузера нет возможности обновить DOM, так как поток выполнения занят. Обновление происходит только после того, как цикл завершится.
Во втором же случае вызовы setTimeout прерывают исполнение вашего кода, давая браузеру возможность обновить DOM. "Даже с 0 задержкой" - тоже ничего удивительного, так как нулевая задержка означает не "вот прям сейчас", а "как только поток выполнения освободится".