Hey Starscream, as far as I know the deadlines are only around December 15 for international students, so I don't think you have to worry about that. I am an international student myself, applying for MS/PhD Electrical Engineering, Fall 2013.
As for the TOEFL, if you are fluent in English you should have no problems with it. My English is fluent, and I didn't do any studying for the TOEFL at all, but still scored 117/120. Some universities state that you need more than ~26 for the Speaking Section in order to be considered for a Teaching Assistantship.
The people above mentioning the importance of a nice and early start on the SOP are absolutely correct. I plan on starting mine as soon as I have my GRE scores, so that I may have a better idea of which universities are realistic goals for me. Be sure to write your SOP specific to each university and program, as I have heard that having a generic SOP can severely damage your case.
Have you taken the GRE? I suppose that would be the most important thing to get done straight away. I am writing on Wednesday, and even though I have a strong mathematical background, but I am still pretty nervous.