For example, if I take a tertiary halide in water + ethanol solution and add I- ions to it (which is a good nucleophile), then shouldn't the reaction be SN1; because SN2 is not possible as the substrate is tertiary. Please explain.
You've pretty much said it all already. SN2 is ruled out at the tertiary centre. Since the attack of the nucleophile in the SN1 mechanism is not rate-determining, it doesn't matter whether the nucleophile is weak or strong; iodide works fine.
In this case, it's more likely to get intercepted by the solvent itself, which is present in much larger quantities and is also nucleophilic, but that's another story.