I can't speak about FRAM (ferroelectric memory), but any technology that uses floating gates to store charge — any form of EPROM, including EEPROM and Flash — relies on electrons "tunneling" through a very thin insulating silicon oxide barrier to change the amount of charge on the gate.
The problem is that the oxide barrier is not perfect — since it is "grown" on top of the silicon die, it contains a certain number of defects in the form of crystal grain boundaries. These boundaries tend to "trap" the tunneling electrons more or less permanently, and the field from these trapped electrons interferes with the tunneling current. Eventually, enough charge is trapped to make the cell unwritable.
The trapping mechanism is very slow, but it is enough to give the devices a finite number of write cycles. Obviously, the number quoted by the manufacturer is a statistical average (padded with a safety margin) measured over many devices.
First of all, the way flash works, in general, is that a write command can only change bits from one to zero. To return bits to one, you must erase an entire erase block. Therefore, you cannot just "write to it like a hard drive". On most flash devices, multiple writes can be made to the same block or even the same byte, again as long as you are only changing ones to zeros. (There are some flash devices where the manufacturer recommends against multiple writes to the same block, but this is rare.)
To answer your specific questions:
1) In general, the endurance is based on erase cycles on each block. You can write individual bits (to zero) as much as you want, but doing an erase to return bits to one will wear down those bits of flash.
2) One way is to use the first byte of each record as a status indicator. It starts, after erasure, as 0xFF. When you start writing the record, you write 0x7F to that byte (zero the high bit). Once you complete writing the record, you write 0x3F to that byte (zero the next highest bit). To mark a record as deleted, you write 0x00 to that byte. All of this takes advantage of the fact that you can always turn a bit from one to zero.
Later, when you're reading records, you only look at records with 0x3F in that byte. 0x7F means that the record writing was interrupted (power fail/reboot) and is invalid. Once an entire erase block has only 0x00, 0x7F and 0xFF blocks, it can be erased.
By the way, you can keep a map of used/free blocks in RAM so that you only have to scan when booting up.
3) See the top of this posting.
Best Answer
There is no limit to the amount of read cycles you can do, but repetitively reading causes something called read disturb. Essentially, reading lots from the same segment without an erase cycle can cause the data to be read incorrectly, and also corrupt surrounding cells in specialised cases.
More info here http://en.wikipedia.org/wiki/Flash_memory#Read_disturb
Most flash controllers will handle this automatically by shuffling data around, it's usually only a problem with controllerless flash such as on a microcontroller