There's a more in-depth article on Wikipedia - the Languages of New Caledonia.
However, the downside for you here is that while English was one of the three main languages until 1853, there was then a concerted effort afterwards to wipe it out.
The closest lexically was Bislama, although the words were different, so that might be an 'easier' one to learn if you wanted to learn some phrases in a non-European language, however, realistically, French is going to be your best bet here, it would appear.
However as you've no doubt noticed in your travels, even in places where you wouldn't expect it, people quite often know some English 'unofficially', and you may be surprised. It's also surprisingly easy and fun sometimes to communicate without words ;)
EDIT: Indeed, according to Wikitravel's article on the area, if you're in Noumea, you may in fact be ok:
The official language is French, and it is difficult to find English
speakers outside of Noumea. In Noumea, French, English, and Japanese
are widely spoken at hotels, restaurants, and shops. To enjoy a place
like this, you should really endeavor to learn some French.