How early should one request a letter of recommendation for graduate school?
Contact the professors now! There's no reason to wait. You can just tell them you are interested in having them write letters for you, if they are willing; they can at least start thinking about what to write. Then as soon as you have decided which schools to apply to, send them the details on  how to submit the letters and the deadlines. I would say this should be a bare minimum of 2 weeks before the deadline, preferably much sooner.

After that, don't hesitate to remind them periodically of the deadline, until they tell you the letters have been submitted.