Трудовой стаж исчисляется в соответствии с ТК, и учитывается в трудовой книжке.
Если вы, например, зарегистрируете ООО, назначите себя ген.директором, пропишите это в трудовой - вот Вам и стаж.
Насчет заграницы, все зависит от страны, ведь требования у всех разные (шенген, гринкарт и т.п.). Для получения более подробной информации лучше воспользоваться официальными источниками.
И какое юр лицо открывать если нас двое таких?
Как таковой разницы нет, хотя, для пары сделок (опять таки, каких следок) лучше ИП, в данном случае меньше мороки с бухгалтерией, налогами и т.д. Вариант на двоих:
1. Регистрация совместного ООО, с разделением долей уставного капитала, то бишь, становитесь равноправными учредителями.
2. Если ИП решите, то лучше подписать договор простого товарищества, он как раз регулирует деятельность физ.лиц без образования
совместного юр.лица.
Надеюсь, мой ответ будет Вам полезен!