These answers are great.
I'll expand a little--
Surveyor/Tax Assessor
From the Anglo-Saxon Chronicle:
Then, at the midwinter [1085], was the king in Gloucester with his
council ... . After this had the king a large meeting, and very deep
consultation with his council, about this land; how it was occupied,
and by what sort of men. Then sent he his men over all England into
each shire; commissioning them to find out "How many hundreds of hides
were in the shire, what land the king himself had, and what stock upon
the land; or, what dues he ought to have by the year from the shire."
Basically, something like the Domesday book, which is an accounting of English lands, was made up by men the king sent. It was informational (like a census of sorts) but it also served the purpose of giving the King a basis upon which to tax their Lords. Because Lords didn't always self-report so well, it was important to have independent assessors look into the value of the lands, what they could produce, the population, general income and all that jazz.
The guys assigned to this ran circuits throughout the Kingdom.
Sometimes a lord wanted an assessment/survey of their own land from someone impartial, and they would tap a specialist who wasn't always local but who was recommended by another lord. So it wasn't always a king who was asking. Surveyors were also sometimes called in by circuit judges as experts to solve land disputes.
Church Overseers
What Kings did, so did the church. The Inquisition is an outgrowth of that function, but it wasn't always so hardcore. Rome wanted reports (not necessarily self-reports) on the state of churches and the dogma taught at various parishes. So there were Bishops whose sole purpose was to travel and send word back to Rome.
Builders/Specialist Craftsmen
If you had a specialist craft of any type, be you a stone carver or a maker of armor, or arms, you might not ever get enough business to stay in one place.
Once you've made armor for the local lord, who is likely the only one who can afford it, there's no reason for you to stay.
It was common for a stone mason or glass worker to move from site to site.
Security and Judges for the Medieval Fairs
I've written about Medieval Fairs in past answers. Basically, there were huge fairs, lasting for weeks at a time where merchants came together to sell their wares. The Champagne Fairs in Medieval France are a great example.
At these fairs, they set standards--measurements of length, weight, standards for each industry participating (from cloth to backed goods).
Merchants there dealt with the public, but they also made deals with each other. During the course of the fair, any merchant there was subject to the laws specific to THAT FAIR. They set everything from fines for cheating other merchants to a ban for certain practices.
It's a really odd thing, because any merchant-type dispute during the fair went to the fair court and the comptroller for that fair--NOT to the regular legal system.
What this meant is that there were often a group of people who travelled to help solve disputes and sit in judgement. The Comptrollers were often local and voted for or they could be someone trusted who travels from place to place. Sometimes they were merchants themselves, sometimes they were retired. Often they needed an entourage of people to help them because they couldn't be in two places at once, sort of junior members to sort out the small stuff, or help settle things so it never has to get as high on the ladder as the Comptroller.
Security for the fairs was important as well--they would roam about with lanterns protecting the goods and generally being muscle when a dispute got out of hand. They did supplement with local help, but they would often have a trusted group that travelled from place to place.
Literally Anyone in an Entourage for Nobility
Nobility, from knights on up, liked to travel--for sport, for politics, and they brought a TON of people with them. The higher up you were the more likely you were to bring a whole dang staff with you. Almost every profession you can think of that a noble might want. A horseman, a houndskeeper, a specialist tracker, falconers, squires, messengers that you sent ahead to let another noble household (or your country house) you were a few days away, people to maintain carts, a cook for the road...if you can think of a purpose, there was a job in it.
Transporters of Goods and People + Guides
Hired out by merchants and nobility, there were people who simply traveled to get stuff or people from point a to point b. Many times by water, but not always.
There were also road guides for tourism, especially pilgrimages. These were not generally religious figures. They knew where to stop for lodging, which wasn't always apparent, because in early Medieval times, this wasn't always an inn. See my answer here about what inns were like and how far apart they were.
A road guide knows who should be bribed and who should be ignored, they know how to avoid highwaymen, where to stay on a route and so on. They also, like tour guides of today, might get a small kickback from lodgings and services for bringing their group by.
Seasonal Workers
Since the fall happens everywhere at the same time, harvests tended to use mostly local labor. This changed with the labor shortages of the Black Plague. If a lord needed extra labor they generally asked nearby lords for people, so prior to the plague, there wasn't as much mobility for this--that is to say people didn't travel everywhere to do this (there generally wasn't enough time in a season to do so) but might go to one particular place in a group of harvesters from one lord to another. Again, this changed late in the period.
Homing Bird Keeper/Transporter
This is a bit obscure, but as early as 1150 in Bagdad, homing pigeons were used to send messages. This wasn't widespread practice in Medieval times, but in fantasy, you can go all George RR Martin with it.
In order to send messages to a place, you have to take the birds AWAY from their home, which means that they have to be cared for on the road, and transported to far away places in a kingdom. So a King or lord that wants other lords to be able to communicate with them, sends a bird transporter all over the country with birds in cages who know their home as the King's castle keep, and they can send a short urgent message to their regent or vassal. And, while you are at their keep, you can take a bird from the king's vassal and bring that back to the king so that the king can send a message to the vassal and so on. Could lead to EXTENSIVE travel...Could be for any lord who just wants a communication network...
Doesn't have to be birds as this is fantasy, can be any homing messenger creature.