Some thoughts on your thoughts:
1) Deva. I'n my mind a newly reincarnated Deva does not totally remember their past incarnantion quite as personal memories. It's more distant than that. They are reborn seemingly at random, although some sages think there is a pattern.
-- This is fine...it could explain why the Scholar likes to write things down so much and keep journals. I'd also like to put forward the notion that a deva can, at times, access past-life memories with immediacy, as if they were fresh and new. That's what the 'Memory of 1000 Lifetimes' racial power simulates. For a Deva, the sensation is kind of like when something's nagging you at the tip of your tongue, and suddenly you remember all at once in a sort of Eureka moment. In my head it works kind of like Dr Who's 'Time Lord Regeneration' (time lords being something of the inspiration behind this concept) in which each incarnation is a new person, with at times radically different appearance and personality...but still has -some- kind of continuity of consciousness, even if it's tenuous and remote.
[Detail stolen from your proposal.] There are an extremely small number of Deva. They are not all incarnated at all times. Most of them have fallen in to a conceit of using only the name of their common profession, as The Scholar has.
-- This is good too...and just to explore it a bit; the small number of devas could mean that only a few celestial spirits chose to become devas in the first place...or it could mean that devas have been around a -very- long time, and that their numbers have dwindled over the years...because it's possible for a Deva to leave the cycle of resurrection, but it's not possible for new ones to enter it. Thus, there's a slow thinning of their ranks over the eons.
They are rare. Most common folk won't recognize what they are, although most instinctively respect them as servants of the gods.
-- Goes hand in hand with the second point, and is therefore good for continuity. Also seems appropriate.
There are two ideas I have for how to proceed.
1) We open the game with only the scholar. The scholar has opened his(her?) eyes for the first time in this incarnation, and we will do a mostly RP introduction of the characters. The scholar will meet the next candidate's three characters and will choose one of them as a companion. We can all say which one we like, but Shayuri gets the final say. The setting is that The Scholar will be near a moderate town fairly isolated and independent of any larger kingdoms. Human dominated, but almost half the population is nonhuman.
-- That'd be interesting, since it would imply that The Scholar 'starts out' at 3rd level.

The only potential issue with this route is that a newly awakened Scholar might lack a driving purpose for which to assemble a group. He'd be more likely to just amble about, goggling at how awesome everything is through his new eyes, until he noticed something where his intervention was needed. I do really like the RP potential of this idea though.
2) We assume the characters are "local heroes". We pick the next character after some talk about how they interact with The Scholar. The opening will be a cold open in a tavern, although that is very negotiable.
-- It has the advantage of being very flexible and player-friendly as far as our backgrounds go, and it lets at least some of us start out already together which can grease the wheels of the first few sessions...but it also robs us of those entertaining first moments.
I feel like the pros and cons pretty much balance on that question, so I'm good either way.