As far as I am aware for the humanities and social sciences (I don't know anything about the hard sciences), most US PhD programs do not require that you already have a master's, particularly since you often get an MA "in passing" after the first two years in the PhD program anyway. However your chances of admission might be increased if you do have a master's - I know plenty of people who failed to get into PhDs the first time around and reapplied after having completed a terminal master's degree.
As for an application timetable, it depends on your circumstances and intended course of study. For the humanities and social sciences, applications are normally due late November - January in the academic year preceeding entry (e.g. I applied in the period Nov '04 - Jan '05 for programs starting in Sept '05, with decision notifications coming in March/April '05).
As someone above said, check out the websites of the universities you are interested in, since they may have different policies and requirements as far as applicants are concerned.