NPC Random Spawns

I have an Idea for an NPC Character. He would randomly show up. You kill him. He randomly spawns somewhere else. Including areas you may have already been to. You can not totally get rid of him until something is accomplished.
The problem is I have no idea how to accomplish: Random Spawn…Die…Random Spawn…Die…Random Spawn…etc.
Would I have to have the AI placed everywhere and a random variable to decide which one is activated at the time and then chose another random variable on his death?
Any Ideas on the easiest way of doing this(if there is one)?