So here’s some of my thoughts on what I’ve done so far, to answer your questions:
Do you play games against each other first to see where you stand and how both mentor and mentee need to grow?
So far my first session has always been having a look at the decklist we’re going to be focusing on / the person is currently playing with, and then jumping into some random games to see how skilled the person I’m working with is. I suppose this doesn’t do much for showing what my own weaknesses are 
.
Do you jump into games against random opponents?
This seems ok for the first few couple games to get an idea of skill level, and if you’re focusing on general play advice so you can look over the shoulder and discuss plays with your mentee. If they’re getting a good grasp of what’s going on, and the focus shifts more to “how do I get the most out of my deck + common matchups” it’s better to play versus them and discuss the game afterwards. You probably won’t need to watch over their shoulder if they have a good grasp of the game, it gives them a good opponent to play against, and you can select what matchups you want to practice instead of facing off against random decks.
Do you think voice chat is better than using some sort of messaging system?
Yes. Could not image being able to discuss anything as effectively without voice chat.
Who decides what decks to play, from the archetype to the individual card slot?
It’s the mentees decision for what decks to play, as they know best what they want to learn 
If they’re unsure, I’ve put out some tier 1 options to try out, and they can take their pick as to what to learn with. I’ve gone for this approach, since it means I can put my time into studying those decks myself so I can give better advice. As for card slots, I’m personally not experienced enough to make large changes to established archetypes, so I go with the version of it that has worked best for me and explain what the tech cards are that you can use if a mentee has a skewed local meta. It’s important to learn to face those decks without the tech cards first, and then later on add them in so you learn what the plays are vs a certain deck instead of relying on finding your Plascrete for example.
When using an over-the-shoulder method of teaching via screen sharing, who does the playing?
Always mentee. I’m a big advocate of “learning by doing”. I’m confident that by doing the motions yourself, you’ll learn much faster than by watching.
Who has the final call on the plays made?
I’d say mentee. They’re the one holding the controls 
. No seriously, if they make an “incorrect” play and lose because of that I’d say you learn a lot more from that, than winning because you pretty much played the game for them.
Clearly any sort of discussion between mentor and mentee will increase
the time it takes to complete a turn - how do you make sure you have
opponents that are willing to be patient with that (From what I’ve heard
of Jinteki, this seems like it might become a problem.)?
Have not had issues with this yet, but I guess if you really want in-depth discussion you’d have to play against your mentee so you have plenty of time to discuss certain plays.
What are the best ways to counter the lag created by the distance between parties?
Haven’t encountered lag (playing with people from US and Australia, am in Europe) myself, but if either of your internet connection is too slow for screensharing you’ll have to resort to spectating them on Jinteki.net. It’s annoying not being able to see their hand, but it’ll have to do