Childcare/playgroups

Have you tried contacting the international schools in UB?
They may be able to assist.

I don't personally know a lot of the expat families here, but some of us with small kids do send them to a private kindergarten ('tsetserleg' in Mongolian). That's what we do with our 4 year old daughter and she loves it.

There are some kindergarten schools that have some teachers who speak English that seem to be aimed at higher-earning Mongolian families and expats. My daughter's previous kindergarten has a couple English-speaking teachers and had a couple other expat kids (it's a good kindergarten but we switched to one that was closer to our home so we didn't have to deal with traffic). Our current kindergarten is good too though doesn't have fluent English-speaking teachers, but as we're trying to encourage our daughter to pick up more Mongolian anyway it's not an issue for us.

As to your specific situation, there are some kindergartens that prefer to have kids 2 and older that are toilet-trained, and if they do take kids who aren't toilet trained they will charge more. I don't think most need to worry about their child not 'fitting in' because of appearance... my daughter doesn't look Mongolian hardly at all and she has lots of fun and friends there. Another thing you can try is to contact your country's embassy in Mongolia and ask if they can refer you to any kindergartens or parents' groups in the area.