Four weeks is an ample period to provide. Two weeks is minimal. If you must ask for a letter in less than two weeks, an explanation of the exigency would be appropriate. Many recommenders ask for a reminder a few days before the student wants the letter in. For example, for law school, sending two from undergraduate instructors is generally a minimum.
Some major fellowships require six.
Whatever you do it never hurts to have extra letters in your house file. As a general rule, you should ask for a recommendation from the person who best knows you and your work. A letter of recommendation from a professor that comments on little more than the grade you made in his or her class is not impressive. In some cases, a professor may co-sign a letter drafted by a TF, and you may wish to inquire as to whether this would be possible. Un-cosigned letters from TFs are not appropriate for some fellowships and are discouraged for applications to many masters and Ph.D. programs.