How many times can flash be rewritten before an erase is required?
I've had recent experience with the Samsung K9F8G08UXm.  This is an 8 Gbit device organized as follows:
1 page = 4096 main + 128 extra = 4224 bytes
1 block = 64 pages
1 device 4096 blocks
Looks sort of like this:

The device is erased on a block basis, or 64 pages at a time.
Once a block has been erased, each page within that block can be written to one time.  A page cannot be re-written unless the entire block is erased.  You can write to different pages within a block at different times; that is, all pages within a block do not have to be written at the same time.