Load the existing texture file into photoshop, edit it, and save it with the same name in the same place.
That's how all re-skinning is done prior to a paint kit being available.
Edit: oh, i misunderstood. What you're asking about is changing a geometry, not changing a texture. That requires the .max source files.