Куда может обратиться гражданин Киргизии, работающий в Москве, если работодатель ему больше месяца не выплачивает з/п?

)))
пусть сначала оформит трудовые отношения, поскольку в суде факт трудовых отношений очень сложно доказать, поскольку никто из "много свидетелей" скорее всего не оформлен по трудовому (или иному гражданско-правовому договору), то и их показания не будут иметь силу доказательств по делу. Более того, если он не оформил свои трудовые отношения (то есть не заключил договор, соответственно, не установлен размер заработной платы, то как он собирается доказывать, что он получал такую заработную плату, Вы ведь не скажите, что ему раньше выплачивалась з/п по карте сбербанка или иного банка))).). Права есть в нашей стране как у наших граждан, так и у иностранных в равной степени.
Если, гражданин не позаботился о своих правах раньше, чем приступил к работе, то даже в суде не доказать, что он имеет право на свою з/п. Это если кратко и без ссылок на ТК РФ. Кроме того, он хотя бы писал заявление о приеме на работу? И у него есть копия этого заявления? Если да, то ещё можно, что- то доказать в суде.

в гос. труд. инспекцию и в суд

Куда ж вы, бесправные, обратитесь-то?
Вас и набирают затем, что вы согласны работать за копейки и прав у вас никаких.

А он уверен в том, что он там работает?

Пусть изначально потребует трудовой договор - потом уже и разговаривать.

никак и никому. Всем будет пофиг.

Ответ: никак и никуда.

Если договора нет, то как он докажет факт работы?

За защитой своих прав иностранные граждане прежде всего обращаются в Посольство или Консульство своей страны

Вряд-ли получиться взыскать. Но натравить инспекцию по труду можно.