My answer is different than the others and some people may not like it. The answers people have provided you are very idealistic. Sure, you may get lucky and get hired based on your "honest" answers and self discovery that you have realized that you need to communicate more effectively and give yourself breaks/vacations. While this is definitely a good thing that you learned, it probably won't get you the job.
You're not the only candidate
Look at it from the employer's perspective. They are interviewing other people besides you. Maybe a lot more. What they want to do is narrow down the pool to a few people and pick the best one. If they interview 10 people and of those 10 five were previously laid off, fired, have extremely short work duration, etc. after the interview there resumes will go in the garbage. A couple of the interviewers don't like the personalities of two of the five people. Those two go in the garbage. That means seven of ten resumes went in the garbage. Now they are down to three and will pick one of those people. Bottom line you are not in the final stack.
Twist the truth
I do agree with the other respondents that you cannot lie. What you are going to have to do is twist the truth to your favor.
Find out if you're eligible for rehire
The first thing you need to do is call the HR departments of your previous companies and ask if you are eligible for rehire. This question does not mean that they would necessarily hire you back but is more of an indication if you left on good terms. If you are eligible for rehire that is a really really really good thing because it essentially means you were not fired. When HR from the company you are applying with checks references this is a key piece of information they ask about.
At the same time a lot of companies will not give out this information and will just provide dates of employment. Reason being they are fearful of lawsuits. If you are not eligible for rehire, and the company does not provide this information, this is a very good thing for you. If you are not eligible for rehire, and the company does release this information to reference checks, this is not a good thing and you will have to come up with explanation(s) of why you were terminated. This is where the information other respondents provided comes in. From my experience most companies do not release this information.
Ask former coworkers to be references
The next thing you need to do (and it sounds like you have already done it) is ask your former supervisors and coworkers if they would mind serving as a reference for you. If you had a good relationship with them, and no performance problems (with that particular individual) you may get a good reference from them.
Make sure the references will be favorable
If you are unsure of what they will say about you I would recommend utilizing a referencing checking service (or if you are light on funds have a friend who is not in the industry call) to call your reference and ask if you are eligible for rehire. Yes, I know that you checked with HR for the official answer but this is something HR, or the person checking references) may ask your reference to get a sense of your reputation, skill set, etc. Essentially do some research on reference checks, come up with a list of 5-10 questions, and have your reference checking service (or friend) ask them.
If the responses come back favorable you know to use that reference. If they do not then see if you can substitute someone else as a reference. As an example, if the person who gave you a negative reference was a supervisor you did a lot of work for, but you also did work for another supervisor (and had a good relationship/project with) try using the later. Backtracking a a bit, in your self reference check with HR also ask who they have your direct supervisor listed as. That way you will know if that information is available to the reference checker if they ask.
Deal with unfavorable references
Let's say you have a supervisor who gives you a poor/unfavorable reference.
If company policy states that they do not provide references other than position title and dates of employment, you can reach out to the HR department about the poor reference you received. Most likely HR will then talk to the supervisor/reference and remind them of the policy of not providing references outside of the aforementioned attributes (or to direct all reference inquires to HR). If you are still feeling uncomfortable about what your supervisor will say do a follow up reference check to be sure they are not bad mouthing you.
If there is no such policy, or they still are bad mouthing you, you can get an attorney to send a cease and desist letter to tell them to stop bad mouthing you and if they don't you will take them to court. This will you about $250-300, so it's not exactly cheap.
Note: This is more of a threat to the company/individual. In most cases, unless what your reference said about you is factually false you would lose the court case. Slander/defamation is extremely difficult to prove. In example, if the reference checker asked your reference if you were trustworthy he could say no. You being trustworthy is just his opinion. If your supervisor observed you carry an office pen out with you he could deem that as not trustworthy. If he observed you pick up a been off the office parking lot pavement and not turn it into lost and found but pocket it instead that could be viewed as untrustworthy. At the same time, if the company says they don't provide reference info other than dates employed and job title will not want to deal with a lawsuit (even if they will win in the end) as they cost the company money and time. It's easier just to tell the person providing the poor reference to shut up.
Final note
My answer is based on my own experience. I have over twenty years of work experience. My last two jobs did not end of the greatest terms but know my stuff well and what I do. Unfortunately I had to use the techniques above, but they did end up working (guess I had some luck too). I feel the people who provided responses to your question have never been in your situation before. I feel it's easy to provide the idealistic advise they have given you when they have not been in your spot. I tried the stuff they said and had door after door slammed in my face when I gave my explanations.
You sound like a smart guy. Unfortunately, communication skills and knowing/asserting when you need to take a break/vacation are not skills taught in the classroom. Some of us learn these lessons the hard way as you (and I) did. Other people are just better communicators and to be honest know how to better play the game. Although things did not work out perfectly for you it sounds like you gained a lot of valuable insight/knowledge on corporate culture which will serve you well in the future. I am sure you will land on your feet and excel in your future endeavors. Best of luck to you my friend!
P.S. From rereading your post it sounds like the reason you were let go from the second job was more of a layoff as it seems the company/management wanted to go with a different approach (that of the other manager/supervisor) than you were using. Sounds like you could just state you were laid off rather than fired (assuming your record states you are "eligible for rehire").
