When I say retexture, I'm specifically referring to altering the stage's texture files, nothing more. In that case it's significantly easier than creating a scratch stage as the workload is exponentially smaller. However, you're also limiting yourself. The most you can hope to get away with is setting changes (a Hyrule-themed Castle Siege, for example) or a season change (Winter/Fall Distant Planet). Everything else would probably look a wee bit odd, unless you're incredibly clever with it.
Creating your own custom stage is a very large undertaking. It's doable of course, but you'll need some solid practice with modeling and texturing definitely, and maybe concepting and animating/rigging depending on the size and scope of your ideas. Most people really only specialize in one these fields unless they're an art wizard, so collabing with folks is never a bad idea. I'm not saying this to intimidate you either, just trying to give you a rough idea.
I can't answer specifics such as Jackal's question because I'm strictly a modeler and texturer, unfortunately, but what I said in my above post about researching methods based on your goals is your best bet. View some tutorials, experiment with the tools in those tuts and practice a ton. Making mistakes is inevitable and mandatory.
I highly recommend anyone here who wants to learn modeling to check out Arrimus 3D on Youtube. He has a gigantic library (100+) of in-depth videos on how to use 3DS Max efficiently.
PM me if you want more specifics.
