With some revision, I would say that the first two sentences are okay, but the third is a bit awkward.
First of all, this simple sentence is just fine:
I need to paint the wall.
If you're talking about existing paint, however, I would phrase it a bit differently:
I need to paint on top of the (wall's) existing paint.
I need to paint over the (wall's) existing paint.
Normally, context will make it clear that you're talking about a wall in the first place—so you often wouldn't need to mention that. (Which is why I put it in brackets.) However, if it is mentioned, the sentence is clearer if the paint is main subject rather than the wall itself.
I need to paint on the (wall's) existing paint.
The reason this doesn't sound completely normal is because it would be more likely interpreted as painting a picture (or something similar) on the wall rather than actually applying a coat of paint to the entire surface of the wall.
It's simply the case that when you draw on a wall, you are drawing on just a portion of wall. The same is true of putting graffiti on a wall. The association with on is, generally, one of using just a portion rather than the entire thing.
In choosing between on top off and over, over would be used in the specific context of deliberately covering up what's already there.
I hate that paint colour. I need to paint over it.
This implies that the purpose of painting is to cover up the existing paint that you don't like.
Meanwhile, on top of doesn't indicate a specific purpose in the same sense. It's just saying that when you apply new paint, you will do so without first removing the old paint.
I would personally tend to use paint over more than paint on top of, perhaps because it's applicable in more contexts, but I don't think there's a problem with using either one of them.