I feel you have no other choice but to lay things out on separate UVs. As you said... Have the Legs on one set... The main Body (Torso) on another, and the arms on another.
It would be ideal to store all of these on a 1024 x 1024 Texture. All the weapons will have there own UV set. Possibly only 512 x 512 As they are allot smaller than the other body parts. As for all the greebles you can put them on they're own Texture.

This will result in about 5 or 6 textures for the final model. BUT everything will be in high detail and everything will have an even resolution.

Plus I don't know about you, but my computer would DIE if I tried to edit a 17,000 x 17,000 pixel image in PS... Let alone loading it into Maya....

Anyway, good luck