I'm not an expert (wait for Smeags, Tbone or Lestat to show up) but:
1 - Yes and no. While you can re-train EVs, natures and IVs do affect stats and cannot be changed. Good IVs can be trickier and time-consuming to get, but there's no excuse to waste time training a pokemon with a bad nature with the tools available nowadays *cough*breedingwithdittoholdingaeverstone*cough*.
2 - Yes. to all. This is the damage formula (quite pretty!) (found in this Bulbapedia page, more info there):
Of course there are plenty of modifiers:
3-1 - Yes.
3-2 - It's the damage per hit both cases. Every hit of Icicle Spear hits for 25 base damage, every hit of Outrage hits for 120 base damage.
4 - That depends on the pokemon. Some are good at playing defense, others offense.
Don't subestimate stat-boosting moves like Swords Dance or Dragon Dance. After 1-2 uses a pokemon with the right moves can be deadly.
As a rule of thumb, go for an attack-hindering nature for your special attackers, and a special attack-hindering nature for your physical attackers.
Oh, and Stealth Rock is overpowered.
