How NAND Flash controllers erase single pages efficiently?
Have a look at this paper from Micron : use a mapping of logical block to physical block. Maintain a supply of pre-blanked pages and write into the next available one (or one chosen by your wear-levelling algorithm).

Eventually almost all your blocks are full, with some holes where pages within the block have been marked "deleted" but not actually erased. Then you do your algorithm: find block(s) with most deleted pages, copy to new location, erase old location, put old location on the "free" list.

This then raises the question of how to store the mapping data itself; one common approach is to extend the blocks slightly and put the mapping data on the block itself (as a "tag"). At bootup the controller can cache some or all of the mapping in RAM. Another approach is to use the NOR flash of the controller itself to store the mapping data.