It would probably be worth your while to apply first to smaller companies in the country of your birth as you should have right of abode there. Perhaps look at airlines later on when you have more experience and a few hundred more hours. Non national airline crew members are usually very experienced high time pilots as most companies prefer to start off their own nationals in the right seat, rather than a foreign pilot.
The best way to get that first job would be to actually arrive on site and begin knocking on doors with your CV in hand. Good luck.