How many cells need to be damaged before a human can feel it as pain?
Although any number estimation would be inaccurate, I can think on two factors that can influence the count.

Cells location: Pain is trigger when specialize cells (Nociceptors) fires action potentials. The density of those nociceptors is greater in the tip of your finger than in your back. So the number of cell damage that trigger the pain would be different in those areas too.
Cell death rate: The delay that you mention is a key factor. Slow death like the normal on skin is done by a regulated mechanism (Apoptosis), in this process the cellular components are recycled. In fast cell death, the cellular components are released causing inflammation, which increases the nociceptors sensitivity.