What you choose to actually model in is irrelevant. All that matters is that you can get the resultant mesh into either Max or GMax so it can be set up and exported using the NWMax script.
I would suggest that if you do not already have any modelling proficiency and are looking to learn, GMax is probably a good place to start. It's a free, albeit crippled, version of Max 4. Although it can't do many things a lot of modern modelling apps can, it still retains the same basic Max workflow and conventions, so it puts you in good stead down the track (Max is the industry standard).
The other main alternative in the free category is Blender. The downside is that it is arguably even more horrible to use than Max, but the upside is a lot of game modding custom content production is centred around it, so there are all sorts of import/export scripts available for various games (like TES and FO3/NV for example). If you aren't angling to pursue a career and modding is just a hobby, Blender might be the more optimal route in the long run.
Regardless of what you model in, if you want animated meshes like heads, you'll have to do the skinning/weighting in Max/GMax. Especially if you are using GMax as your export vector, as your import options are very limited, so the chances of importing a fully rigged and weighted mesh are virtually nil.