I have reached level 20 on warlock, if I create a new character what level will it start out as? and do I have to do the whole story over again?
Each "new" character you create will be level 1 like before, and You will have to go through story missions again. there is a few "new" features you will have available to your new character, though.
Firstly, if your first character is level 15+ (yes, in your case), you will be able to switch between subclasses freely on your new character. EX. You could start as a Defender.
Second, all of your glimmer is shared between characters, so buying gear for your new character will be a bit easier.
Third, the Vault is shared between characters as well. if you got a nice item for a different class that you plan on building, go ahead and vault it for them!
And finally, weekly and daily missions are bound to the character, so you could effectively double and triple your strange coin/ascendant farm if you have all three characters strong enough.
Every new character you make starts at level 1. If you already have a character on that account that is at least level 15, you can have access to two subclasses initially instead of one (i.e. if you're a Hunter, you can do either Gunslinger or Bladedancer first, instead of just Gunslinger). You still need to be at least level 25 on the character you are currently playing to unlock TTK subclasses though.