I put together maps of the characters you can reincarnate into in part for my own use and in part for fun. I got the locations from the Nomad Soul fansite www.mayerem.fr. These maps do not show characters which are beyond the mapped areas. Characters which you will automatically reincarnate to by dying at certain points can be found later if you avoid those deaths, and those locations are also included.

That's actually useful, I wish I had something like this in my first playthrough. I also found this:

http://www.gamefaqs.com/pc/193073-omikron-the-nomad-soul/faqs/6617

This page lists the characters' abilities, but the locations are quite vague, so your maps supplement it well. Reincarnation is a great mechanic, but I can't help feeling it could've been used to a greater extent. So far it's only a gimmick, or a way of avoiding death. I wish there were character-specific skills in the game. Like when you need to pick a lock, you have to reincarnate in a thief, since monks or policemen don't know how to do that.

These maps make the game look so tiny. I remembered when I played it first it felt like there were hundreds of characters available.

If you are asking how to get Nuyasan to appear, all the guides I've found simply say he appears in the temple "at some point". I have seen him there myself, but I'm not sure when it is triggered. It is at least after the point where you are forced to leave Kay'l behind.

Personally what I would like most added to the game is for each character to have their own social environment (friends, work, etc.) like Kay'l, so it would feel like you are actually infiltrating their lives and they are not just different graphical models with different statistics.

Almost all of the inhabitable characters come with their own apartment, furnished and decorated to reflect that character's personality. It's not the same, but at least it's something. Even with a smaller number of character it would've been hard to implement a more immersive social setting for each, especially considering that the game feels rushed and unfinished in many places.