Hi!
The best for the visa is to call/go to the French embassy & ask.
I personnally have no idea (as I am French!)
Regarding the job, hum, well I don't really know but without speaking French, except if you have specific skills like knowledge in nickel treatment or construction or whatever job is searched in New Caledonia, I guess it could be very hard to find...
Maybe you can have a look on the website and make a search in the google space above like "bartender job new caledonia"...
Good luck!