methods early in Java - before objects
The two general approaches to teaching OO that I've seen are "objects first" and "objects last".  Objects first takes the notion that, since we are teaching OO, we should start with instances, APIs, method calls, and inheritance.  (See Greenfoot as an excellent start to an objects-first curriculum if you are interested in exploring this approach.)  Eventually, you start to delve further into the nitty-gritty of the language, adding in arrays, loops, mods, etc, etc, etc.

Objects last follows the historical developments more directly, teaching imperative programming without OO first in order to highlight some of the thought process that went into developing OOP in the first place.

If you are taking an objects-last approach to your course (and it sounds like you are), then methods naturally fall before objects, and need to be included.  Methods were an important development for both code clarity and code reuse.  Though it's true that everything will need to be static at first, you can either leave this in as a temporary magical incantation, or make note of it as something exciting that will come later, and that about two-thirds of the way through the course, you will flip everything on its head, and those static markers will largely go away.