I was having a debate with my brother the other day, about this question. He claims Clara is the longest time companion because she helped every incarnation of the Doctor. (little spoiler from Series 8):
Even since his childhood, as we witnessed in "LISTEN"
That can't be right because those were Clara's echoes for the most part. My counter answer: Handles, the Cyberman head we met in The Time of The Doctor.
The Doctor got stranded in Trenzalore for 300 years, waiting for the TARDIS to come back after returning Clara home. During that time, he probably saw three or four generations of Trenzalorians (is that word right?) live their full lives, but Handles remained by his side after finally breaking down when the TARDIS and Clara returned 300 years later.
I'm not very familiar with Classic Who. It's been impossible for us to get access to those episodes here in my country. Is there a companion for the Doctor who travelled with him for more than 300 years? My first guess was Susan, but I can't find information on how long they travelled after leaving Gallifrey.
TL;DR: Well, the title. Does Handles have the record for being with the Doctor for the most time?