First: Know the Rules
There is a big difference between being an established player in a game and knowing every detail of the game and being able to relay it to a new player without having to pause and look up the rules. Go through the rulebook again and again and then play several solo games (3-4 investigators). They say the best way to learn something is to do it yourself. This same sentiment has been echoed elsewhere on the Geek, but it still rings true. Also, while you play through the solo games, you'll be able to identify problem areas and reinforce them after going through the rulebook.
Second: Explain the Character Sheet
I try to have the game set up ahead of time before the players arrive and I've pulled out investigators at random. They all have their fixed items, but I let them draw the random items themselves (helps reinforce what each deck of cards is). As they are drawing random possessions, I give a run-down on the character sheet. I start from the top and explain everything from the top-down. I when I explain stats, I don't explain all the details, but instead give a short thematic explanation for the stat, which will help them adjust their stats for the start of the game. I usually emphasize the speed stat the most at the beginning ("speed is how many spaces you move in a turn") because that's something that's easy for most players to understand and they can instantly interact with the game knowing just that.
Finally, after I explain the character sheet, I briefly explain the dice mechanic and how it applies to the game sheet (this stat shows you how many dice you'll roll to make a check. If you get a 5 or a 6 on any die, you win. The cards and monsters will either add or take away from this number.)
Third: First Mythos turn
This part of the teaching is crucial because it lets everyone in on all the bad stuff a) as a theme and b) as a mechanic.
Explain that the card is read upside down and backwards and go through step-by-step what happens and when.
1: Gate opens
2: Monsters Move
3: Clue Token Appears
4: Special Effect Resolved
Fourth: Explain the phases
When it comes time to teach the game, start by giving a quick run-down of the overall game (whacked-out stuff is happening in Arkham, Mass. and monsters are pouring out on the streets. An Ancient Demigod is about to pour into Arkham and it's up to us to stop him). Also, give a short description of win/loss conditions right at the beginning. This lets them know what they're trying to get at from the get-go so they aren't fumbling around the board trying to figure everything out.
Starting at Upkeep, then Movement, Arkham Encounters, OW Encounters and Mythos, explain in 3 sentences or less what happens in each phase. As you play through, announce each phase and say exactly what you're doing in each phase, then coach each player through that phase. For this purpose, it's generally a good idea for the teacher to start as the first player on the first turn so that you can explain exactly what you do and everyone else can learn by example.
Fifth: Don't get bogged down in the details
This part is the most important. Don't try to explain the whole game at once. Instead, coach players through each step as it happens. Examples: As a monster moves, say "Crescent monsters move this turn. However, this one has a yellow border, which means it never moves." or "When you fight a monster, you make a horror check only once at the beginning of combat. After that, you can either fight or flee. If you fail, it deals damage, after which you can fight or flee again.)
Deal with stuff as it comes up and not all at once. You don't want to overload a person's head with all the rules so that they're trying to remember everything instead of having fun.
Miscellaneous
Go slow and give examples where you can.
On each new card/token type that comes up, briefly explain in order the different parts of that card, then coach that player through the actions on it.
Announce every phase as it starts and ends and encourage players to act in order instead of rushing ahead or all at once. The more chaos by the players, the more confused a slower learner may get.
Let the new players have an active part in the game experience. Assign roles to each player (setting out gates, setting out clue tokens, adding a token to the doom track, collecting dice, etc) and let the players read encounters to the person it's happening to. That way, whoever gets the encounter gets a better dose of the game theme and the reader also gets to look at the card and participate in the decision that must be made.
Most of all, have fun! Celebrate your victories and mourn your losses. The more fun you have, the less the mistakes made matter.
Now that we finally "got" the whole thing we played 3 or 4 rounds and left the board to continue tomorrow. 
