まずはご自分でできることからはじめてみては?

ヤフーやグーグルなどの検索エンジンに「ニューカレドニア」「移住」と入力するだけで、supra524さんの知りたい情報がある程度見つかるのではないでしょうか?

例えばこんなサイトとか。
http://www.interq.or.jp/tokyo/ystation/nc.html

彝驫靉さんも仰られていますが、外国で働くと言うのは大変ですよ。

言語能力が要求される場合もありますが、それ以上に「なぜ現地人ではなくわざわざ外国人を雇わなければいけないのか?」ということを現地の当局に雇用者は説明させられるのが一般的だと思われます。

つまり、どの国でも現地人の雇用を優先しますから、現地人にはできない仕事をsupra524さんができるかどうかが海外で働くことができるかどうかの条件になってくるでしょう。

ちょっと覗いたニューカレドニアに移住した方の話からも当地もやはりビザの問題は大きく、簡単ではないようですよ。