This is a "Wild Mass Guess" entry, where we pull out all the sanity stops on theorizing. The regular entry on this topic is elsewhere. Please see this programme note.
The Medicine Seller is a benevolent mononoke.
He(or his family, or his girlfriend, or his dog, or whatever) was killed by a mononoke, and then perhaps the spirit of the Sword of Exorcism clinged onto his desire for vengeance, and now he wanders Japan, hunting down mononoke. I have three reasons for believing this:
He has crazy powers that no normal human should have.
He never ages. The final arc is set in the 1920s, while all the previous ones were set in the Edo Period.
In the final scene of the final arc, he announces that he will continue to hunt mononoke as long as they exist... and then his sword does the teeth thing, something that it usually only does when the truth, form or regret of a mononoke is discovered, suggesting that this is the Medicine Seller's Regret.
Of note, this can also be interpreted as his Reason (depending on what particular Fansub you are watching, "katachi, matoko, kotowari" are translated either as "Truth/Form/Regret" or "Shape/Truth/Reason". (In Japanese, technically all three words can be translated as "truth"—"truth of form", "truth as it is", and "truth of motivation" respectively.)
A bit of secondary evidence pointing to "Reason" or (more accurately) "Motivation" as well—in the (nonrelated) Breath of Fire IV, particularly the manga, dragons are described as the kotowari of the world (the Something-Or-Other Fan Translation goes with "truth" with the translator's note "Sort of a truth of the world", whilst the official game translation changes this to describing dragons as the force that moves the world). This is what we get for Japanese having different words for different varieties of "Truthiness" that are not directly translatable in English.
The Noppera-Bo arc suggested that the real Mononoke behind it is The Medicine Seller.
Ochou was the real mononoke in that arc. The mononoke wearing a Noh mask was implied to be an illusion created by the Medicine Seller to help free her.
And this could be quite plausible; among other things, there is such a thing as "shamanic noh" theatre (specifically done to cast out such things as mononoke and other Troublesome Spirits) and (as the previous Troper noted) the Mononoke In The Mask even explicitly makes reference to being an actor.
And even the Medicine Seller makes reference to essentially this in a roundabout way—after facing the Mononoke In A Mask after some Nightmare Fuel involving having his face stolen, he even explicitly notes that "I can make any face as my own if I need to". Which is pretty much the entire principle of using masks in shamanic work. (This Troper's opinion: the "Nopperabou" arc is basically a shamanic noh performance seen through Ochou's eyes.)
His dress is also a giveaway; in the same link above, it's noted that the Medicine Seller has the trappings not of a merchant (a very low-class caste in Edo-era Japan) but trappings pointing to the imperial if not the overtly divine. Specifically, he has three facsimiles of the Japanese imperial regalia, denoting him on the low end as a Being Of High Rank.
There has also been an alternate theory that the Medicine Seller is less a mononoke and is rather ridden/possessed by one—specifically his alter-ego. Ironically, a lot of this speculation has come about specifically because of the Nopperabou arc (and the various theories surrounding this).
Another theory that all what is going on in there is a Kabuki play and Medicine Seller has a real-life prototype kabuki actor Mizuki Tatsunosuke (born at 17th century) who was famous not only for his talent but also for making lilac head cloths a cool fashion trend back at his time. Mizuki left stage at age of 30. So make a guess who could he become...)))
Regarding the Medicine Seller's benevolence—there has been a very good argument made that the Medicine Seller is actually acting as an "ayakashi's advocate"—that is, he really doesn't give a damn for the humans, but rather works solely to sever the fetters (created by humans) that have caused an ayakashi to "go mononoke". In other words, there is a very plausible argument that the Medicine Seller's entire purpose in the world is to Shoot the Dog.
This troper actually read a fanfiction that suggested the Medicine Seller was a deity (specifically Inari), and the switching between his normal and mononoke-slaying forms is effectively him abandoning his mortal body for his divine form.
He has a lot of fox motifs. Maybe he is a fox spirit? In the Bakeneko arc, when one of the passengers metaphorically suggests that the disturbances are the work of a "fox spirit", he protests that this is not how fox spirits behave. Of course he would have extensive knowledge of every kind of demon out there, but perhaps he actually knows that firsthand...
The Zashiki Warashi arc takes place in Nagasaki.
It potentially explains the coloration of the characters. Shino is the product of Dutch liaisons with Japanese women, who could have children with recessive blonde/blue-eye traits that, if two of these children had children themselves, might results in a blonde-haired, blue-eyed Japanese girl. Some of Tokuji's ancestors would have been black or South Indian slaves, who European traders sometimes brought with them. A bit of a stretch, true, but possible.
The Zashiki Warashi Arc might have ended with Shino pregnant with the mononoke
At the end of the episode, she starts bleeding , which might suggest that the innkeeper and/or the mononoke might have terminated her pregnancy. She's tied by the red string of fate to her child (Represented by the sole doll), and surrounded by many other dolls with unattached red strings. Her child starts cracking (Miscarriage), states she can't be its mother, and is then attached to the mononoke. Her stomach is much smaller than before, and she might have willingly terminated, or accepted her original child's death, because that means she would no longer be attached to her lover.
The Medicine Seller Only Exists When and Where a Mononoke Exists
Maybe he only appears some time after a mononoke is formed, in the same area. Or on a mode of transportation traveling to the mononoke's domain (since, for instance, he cannot materialize in the middle of the ocean).
The Medicine Seller Isn't Immortal, He's Just Able to Travel Through Time.
He appears immortal because he can phase through the space-time continuum and appear wherever a mononoke problem exists. If The Medicine Seller IS immortal, then there's a very good chance that....
The Medicine Seller Is A Time Lord.
Yeah, every magical character gets declared a Time Lord at some point, but the case for the Medicine Seller being one may be better than average. Think about this:
The Doctor is a Time Lord who concentrates his interest around Britain. As such, he's adopted the culture and dress of his population of interest (although he tends to dress in a flamboyant version of British clothing.) The Medicine Seller is the same, concentrating his interest around Japan. (And The Medicine Seller's duds could certainly give Colin Baker's "Coat of Many Colors" a run for its money in terms of ostentatiousness.)
Traveling Time Lords tend to not be known by their names, but rather by titles they choose for themselves. (The Doctor, The Master, The Rani, and now, the Medicine Seller.) The Doctor's "doctor" persona gives him an air of authority and wisdom which makes other people more inclined to listen to him. Likewise, the Medicine Seller's persona is carefully designed to let him travel around Japan without much suspicion (at a time when people rarely left their home villages,) and his shamanistic look also makes people more inclined to believe he is capable of dealing with mysterious and mystical phenomena. (Think about it. If weird, unexplainable stuff breaks loose, you'd be more likely to believe that a guy dressed as a wizard could handle it, rather than a guy just dressed as an ordinary schmo.)
Like The Doctor, The Medicine Seller (or MS), has a strong sense of social justice. He's less inclined to try and Save Everybody (and will usually leave unrepentant murderers to their grisly fates) but it's clear he cares for and tries to protect the innocent if he can. Like the Doctor, he can be snarky and aloof at times, (and will have no qualms jerking around any human who displays selfish or cowardly traits.)
Like The Doctor, the MS's primary motivation is to travel and fix whatever problems he comes across. (Unlike the Doctor, his actions are concentrated mainly towards healing a series of space-time rifts which have popped up in Japan, which allow other-dimensional beings (mononoke) to slip into the human universe. These mononoke may actually feed on human emotion and thus seek out areas where traumatizing events have occurred, using these events as a catalyst for crossing dimensions. There may be other mysterious phenomena which may lead to the appearance of mononoke (which are widely regarded as gods and monsters by Japan's human population,) but in any case, the MS's primary job is to kill the mononoke and seal the hole leading to its home dimension. He does this using hi-tech tools which he designed himself (a sealing device, sensing and barrier creation devices) which have been made to fit in with his shamanistic persona. (He either did this as a matter of personal preference, or because tools with a more space-age appearance might confuse the people he is trying to help.)
Unlike the Doctor, the Medicine Seller has no Companions. (Although given his line of work, a screeching, emotional human companion would be a liability to him, not a help. Even a competent companion would be problematic, since he/she couldn't use the Time Lord's tools and would need to be protected from the mononoke by the Medicine Seller.) The Doctor only has Companions anyway because his journey is one of wonder and exploration, while the Medicine Seller is more interested in eradicating a certain type of problem.
Speaking of The Problem, the Medicine Seller might have even been sent to Earth to deal with said problem by the council of Time Lords. Perhaps the MS was a Time Lord Criminal, and sealing the dimensional rifts in this part of the universe was his punishment. It's clear in one episode of the series, that the Medicine Seller's greatest fear is that he'll disappear from the world. It could be that the Time Lord Council threatened him with erasure from the Space/Time continuum if he failed to perform the task they laid out for him.
The Medicine Seller's TARDIS is his medicine chest. It's what he uses to travel through time and space. (in the Original Doctor Who, it's shown that only the main console is needed to travel through time, one merely has to be touching it. The rest of the TARDIS is just a container. So a TARDIS doesn't need to be something which fully encloses a character—it could just be something that they either touch or which they can operate via remote control.) It's clear from the medicine chest's operation that it's far bigger on the inside than on the outside (given how many scales it can hold.) and not only can the medicine chest travel through time, it can also open pocket dimensions and project illusions (things the Doctor was never inclined to do, but things the Medicine Seller would have needed to do in order to deal with mononoke in an effective way.)
The Sealing Sword is the Medicine Seller's primary tool for mononoke destruction, but in order to use it, he needs to gauge the full parameters of the mononoke (up to and including the circumstances which led to its entering our world—its "catalyst", which may be linked to the mononoke in space-time.) The Medicine Seller uses his tools and investigative abilities to suss out the information he needs to deal with the problem and to resolve the human emotions which led to it. Only after all the data (Form, Truth and Regret) has been gathered, can a presumably highly dangerous and resource-hogging weapon like the Sealing Sword be used.
How to explain the Medicine Seller's "Hyper-Mode" persona? Well, the classic series had Romana swapping bodies so her character could be played by another actress; (the scene itself was considered controversial, as it seemed to imply that Time Lords could swap bodies without regeneration, which some fans of the series refuse to accept as canon.) But let's assume for a moment that it's true—a Time Lord can change bodies without regenerating, or at least, without regenerating FULLY.) The "sealing sword" which the Medicine Seller uses might give off a dangerous aura (or it might be the kind of tool which can be used only by someone with certain physical characteristics, high stamina, etc.) The body which the Medicine seller switches to whenever he uses the sword could be one he keeps in a pocket dimension and which he dons like a hazmat suit whenever he needs it. Doing this might require a regeneration-like transformation sequence, (but it doesn't "count" towards an actual regeneration. At least as long as the MS returns to his original body after using it.) Mononoke sealing is a niche field which requires a set of very specific, highly unusual tools, tools which a generalist like The Doctor might never had reason to stumble upon. (Hence the reason we never see Time Lords "temporarily switching to a hyper-mode body" in the Original series.)