After weeks of coder's block, the way scenery chunks are added is satisfying to me. In the first video, the pink marked tiles represent the tiles seen by the actual in-game camera, chunks are added only if an empty tile becomes visible. A tile "prefab" is picked randomly, depending on the available space. Tile "prefabs" can have varying size (to allow big chunks that contains big monuments and pyramids or complex arrangements, or small bits of forest or town). The heuristic gives a good enough result for me for now, would be better if it could do several passes.
The second video shows how it actually looks in game (no empty tile, there's still some popping sometimes because tile visibility doesn't take the chunk's height into account yet).
Now I need to be able to fill these chunks with stuff (palm trees, monuments, cities, groups of crocodiles...)