You are right to want to avoid creating the nested structure to begin with. I imagine you read my answer in the question you linked (the second one). As there, here the solution is to use mapcat instead of map. And as I also say in the comments there, while mapcat-indexed does not exist, you can just pass an extra (range) argument to get numbering.
(defn visible-nodes [tree]
(mapcat (fn [idx ele]
(map #(cons idx %)
for [node (cons []
(when (:expanded ele)
(visible-nodes (:children ele))))
(cons idx node))
(range), tree))