Why do tattoos persist if body cells are regularly renewed?
First, tattoo pigment isn't injected into cells. If you were to puncture a cell with something the size of a tattoo needle, it would die - full stop. Many cells are destroyed in the process though, mostly by tearing, which initiates the wound healing process.

So what actually happens is the particles lodge in between the cells of the dermis (the layer below the epidermis, or outer layer of skin) and new cells crowd around it as damaged cells are replaced.

Since the particles in good tattoo ink are too big to be carried off by macrophages, they just sit there. That doesn't stop them from trying, though. Macrophages take up the pigment but are unable to escape with their garbage. Fibroblasts envelope the particles, both intracellularly and within the extracellular matrix they generate. At the end of a fibroblast's life, its contents are taken up by the same process - still too big to remove.

Smaller particles will be carried off by macrophages capable of both consuming the particles and migrating into the lyphatic system, which is why some ink fades more than other kinds. Ink composed of fine particles would be expected to fade severely. New tattoos are also sharper because some of the ink that was injected is lodged in the epidermis, which is the layer that grows out and is shed over time.

In this biopsy of a tattooed mouse, you can see how the epidermis has carried some of the pigment out of the skin while much of the dermal layer's pigment has been either removed lymphatically or enveloped:



Source: Tattooing of skin results in transportation and light-induced decomposition of tattoo pigments--a first quantification in vivo using a mouse model.

Thus, over time the pigment will be moved around a bit by this cellular activity, in fact deeper into the dermal layer on the whole.

The intent of using laser light to remove tattoos is to break those particles down into smaller pieces burst any cells containing them - again initiating the wound healing process. However, unlike in previous cases, when macrophages reach the site they can now sweep the remaining particles away to the lymph nodes.



Sources


General - Tattoos and tattooing. Part II: Gross pathology, histopathology, medical complications, and applications.
Process - Cutaneous Wound Healing


Secondary sources:


Fate of tattoo pigments in skin (pdf)
How Laser Tattoo Removal Works - Smarter Every Day