Так в чем вопрос?
2) Заведи логин на яндексе, залезь там в настройки, выбери страну, город и т.п. - и потом грабь xml из-под этого логина. Способ не лучше первого, но возможно проще - надо будет сначала ломиться на login за сессией и потом этот sessid передавать при каждом запросе, при этом на остальные хидеры можно будет забить.