Littlequeen & PreciousBaby;
I'm not sure whether your children would be interested in a playgroup; if so, you should have a look at the Blossoms (earlymandarin.com). My 2yo dd participated in a handful of sessions before she began nursery school and thoroughly enjoyed herself. The group leader, Linda, seems to have good and standard Mandarin. I am not proficient enough to be able to detect regional accents, so I cannot say whether she has Beijing-accented Mandarin as you prefer, but whatever accent she has, it is not strong. She may also be amenable to doing one-on-one tuition; again, I don't know about this.
Littlequeen, I think at 4, the children prefer to be in a group, even a very small one. I speak from my own children's experiences. One adult and one child does not really interest my two (2 and 4) as much as throwing some other children into the mix, although with an engaged teacher, this can work too. They go to a French playgroup that is essentially just the two of them (sometimes a third child joins in) and they love it. I find that more than four unaccompanied children per teacher really takes away from what the children can absorb, language-wise.
For the Blossoms playgroup, at that time it was a parent-and-child group as the children were younger, and the children did not really interact with each other, although they did interact with the teacher. There was a wide variety of activities to keep them occupied during the hour--songs, dance, bubbles, cars, active games, stories, etc...
Hope this helps.