The 1st Doctor episode Mission to the Unknown did not feature any companions - or even the Doctor himself (not even briefly, as in Blink)! (The Doctor wasn't traveling alone, however).
In some ways, many of the 3rd Doctor's early episodes did not have a companion, because he could no longer travel, having been confined to Earth by the Time Lords. However, the Doctor's assistants (Liz Shaw, Jo Grant), really play the same role as companions, so I'll consider them the same.
Other than those, the only serial in the 1st through 7th Doctor's TV episodes to not feature a companion was (as you mentioned) The Deadly Assassin. I can't recall any novels or other tie-in media that featured such stories.
The Doctor Who movie, which introduced the 8th Doctor, has the Doctor traveling alone. Like in later episodes, the role of companion is filled by another character (Dr. Holloway), and she is offered (but refuses) the role of companion.
Between the Doctor Who movie and Rose, there are various audio dramas, but no TV episodes. In the audio dramas, the Doctor does have companions:
- Charlotte Elspeth Pollard (Charley) becomes the Doctor's companion after the events of the movie, and eventually becomes the 6th Doctor's companion!
- Lucie Miller is the 8th Doctor's companion after Charley.
The most recent of these audio dramas was released in 2009, and there is still time between that episode and Rose, so it's not yet known how the Doctor came to be traveling alone, for how long (at that time), and what he did during that time.
The 10th Doctor mini-episode Time Crash does not feature a companion (it does feature the 5th Doctor!). Earlier multiple-Doctor serials (The Three Doctors, The Five Doctors, The Two Doctors) did show the Doctors with companions.
As you mention, both The Runaway Bride and Voyage of the Damned show the Doctor traveling without a companion, although a character plays the part of a companion (and in one, ends up being one, and in the other, is offered the role). The Next Doctor is similar to this, although
since Jackson Lake believes he is the Doctor, and Rosita Farisi is his companion,
there is a companion of sorts.
The other episodes at the end of the 10th Doctor's time are similar, with Lady Christina de Souza filling in as a companion in Planet of the Dead and no-one in the companion role in The Water of Mars. While many former companions make an appearance in The End of Time, the Doctor is traveling alone at that time as well (Wilfred Mott plays the companion role). The 11th Doctor does describe himself (to Amy Pond) as have having been traveling alone for a while after this time, so this time is considered 'companion-less' by the Doctor, at least.
