You need to strategize with your advisor, or a trusted mentor, about this. You need recommenders who have a high opinion of your work, are willing to put in the time to write a good letter, and know how to do so (which rules out more people than you might think). Ideally, you need advice from someone who knows what sorts of letters different people write and can help you choose who might be most appropriate.
What I recommend for my students is:
A letter from me, which will discuss in detail what they have done, why it's important, what the student's key contributions were, what the future might hold, etc. I'll also sit in on a class the student teaches and talk with them about teaching, so I can put in a reasonably well-informed paragraph about that, but the focus of the letter will be research. (I'll have a different version of this letter, which emphasizes teaching more, to be sent to highly teaching-oriented jobs.)
A teaching letter from someone in the department who is well known for excellent teaching and can evaluate the quality of their teaching.
A research letter from another faculty member in the department. This will be from someone the student has met with at least a couple of times each semester for the last year or two, if not more often, so they will be in an excellent position to write a serious letter.
A research letter from someone at another university, typically someone I know who has interacted with the student at conferences, seen the student give at least one talk, and read at least one paper by the student. This proves that the student is developing a reputation outside their university, and it supplies a letter from someone who has less of a vested interest in seeing the student succeed.
Of course, it's hard to set up (3) and (4) on short notice. It's often helpful if your advisor asks someone. I can say "You remember my excellent student Alice, the one who wrote the paper on X? She's graduating this year, and I think she's going to do very well on the job market, but she still needs one more recommendation, and we're hoping for one from another university. Could you help?" By contrast, there's nothing a student can write that will be as effective. (From a student's perspective, the letter is a favor to the student, but faculty sometimes think of it as a favor to the advisor.)
The biggest problem is if your advisor can't or won't help with this. Then you'll have to pick the most supportive people you know and ask them yourself. It's helpful to offer to meet with them to tell them about your work, to make sure they are fully up to date. You should send them copies of all your application materials. It's also helpful if you supply additional background and commentary, to help give them more of a feeling for your work and its context. This makes it easier to write the letter, by supplying interesting ideas and facts the letter writer can mention. (That's the lazy approach to writing a letter, but if someone is going to be lazy, you want to make it as easy as possible for them.) Make sure everyone writing a research letter actually plans to discuss your research. It can really hurt your application if a letter just says "Bob took my advanced phrenology class and received an A. I was particularly impressed with his insightful questions regarding retrophrenology, and I became convinced that this bright young man has an extraordinary future in pseudoscience. I haven't read any of his papers, but his advisor assures me that they are wonderful, so Bob has my strongest recommendation." When you get your Ph.D., you should be judged based on your research (and teaching), not your performance in classes.
You should request letters at least one month before the deadline. It doesn't really take a month to write a letter, but it can take a number of hours (looking at papers and application materials, thinking, and then writing). Any given week may be very busy - for example, someone may be travelling or facing a major deadline - and faculty members often have to write dozens of letters, so if you do not ask far enough in advance, then there may simply not be enough time for your letter. If you need a letter very quickly, then you are asking for a huge favor, and the letter probably won't be as long or compelling as it might have been otherwise.
As for some of your sub-questions: The writer does not need to know the student well, but must know something about the student's work (for example, from papers or talks). For most academic jobs in the fields I know about, there is no way to avoid submitting recommendations with the initial application.