For the proof of residence, an option nowadays is to book a place long term on airbnb, say 6 months or more, and then put the utilities in your name. Even just one utility may be enough, like water or electricity, maybe even internet too. Then you can use the utility bill as proof of address without needing to sign a formal rental agreement. Note that most governmental places will not accept an AirBnB receipt as proof of address, but a bank might. Keep bills of everything. Always have copies of everything on hand (passports, work contract, birth certificates, visas, bills) and keep electronic copies that you can print off any time.