If just as family names, not just temporary patronymics ( eg: fitz-, or son of, etc. ), then I imagine that it started over Europe rather than in Britain alone. Possibly in France and/or the Empire.
Not to mention other cultures with surnames such as China or India.
Habsburg as a name dates to the mid-11th century.
If my surname was based off my father’s profession… It would be the same as it already is. Eliahna Manwhore. No, I jest. It’s Turner, and though he has had a variety of careers - butcher, welder, concreter, backhoe driver - he has spent the largest part of his adult life working as a fitter and machinist, and he is a woodturner by hobby.
As a child, I would have been Eliahna Bookworm.
These days, I see myself as Eliahna Geek, or perhaps Eliahna Techie.
I already call my boy Tom Tom the Programmer’s Son, so I nominate Tom Programmerson as his name. My daughter would have to go by Flamehair for her most outstanding feature (bonus: her brother could use this name too).
Not really. Horses were for rich dudes. People used oxen, mostly, although it depends on the region. I agree that any village smith would be super busy, but not for that reason. Yeah, some villages will have had two, but mostly it would be one “business” - one Smith +apprentices or a family of Smiths (Father and sons or brothers, or widows and sons even).
A lot of everyday smithery could probably be at home, much like some people today can fix a loose wall socket without calling the electrician. You don’t really need special tools to make a nail, for instance.
I’d be something like “Writer” or “Mathie”.
They got married, right? 
The Romans had family names.
I like my lastname’s meaning of Wolf and use Mountain in games, both in Basque.
Smiths didn’t just shoe horses, they also made tools, nails… there were specific names for each, but a village smith wouldn’t say “oh no, I’m not going to fix your tool, madame! I’m a farrier, not a blacksmith!”
I like some of the old Norse bynames, like “Blood-Axe” or “Skull-Splitter”.
If I had to go by my own occupation, it would be very unimpressive.
My dad had an OK name, so a patronym would not be too bad.
Hometown name would be OK, although my town has a Spanish name, and I am about as W.A.S.P.ish as a person can get.
These.
There are a ton of weird surnames in Spanish, I have known people with the Spanish equivalent of coiffed, skinny, bastard, shorty, horns, muddy, cow head, big head, vicious, etc. I am going to guess they were not chosen by the person in question.
An important point that should be considered as highly likely in how such things were done. Most likely the unflattering or overly descriptive names were not picked by their bearer, but by the community around her/him. Names like Snakebreath and Asshead probably came as a result of behind-the-back snickering and joking. The bearer, not wanting to be regarded as hypersensitive would just go along with the monicker and carry it proudly. I’ve known quite a few older people who are still known my childhood nicknmes like Stinky, Pooter and worse.
Yeah, I was generalizing a bit when writing the OP. According to legend, China started with surnames around 2000 bc, but we’re not quite sure, and the Romans had surnames, but they weren’t inherited in the same way the modern system works. The rest of Europe, I believe, started using them around the same time as Britain.
Roman surnames (nomina, not cognomina) were inherited in Rome from father to children. They showed membership in a clan, a bunch of people who were notionally descended from a common ancestor.
Later on, cognomina could be inherited, too. My grandmother’s relatively rare maiden name is attested as a relatively rare cognomen in pre-imperial Rome, though we* faded into obscurity in he 4th century BC.
*Yes, I know it’s totally a coincidence. I don’t care.
I met a woman with the surname Hempseed. I thought it was pretty cool, but it turned out she chose it after a divorce where she wanted a “rebirth”.
I always wanted to change my name to Hugh Bastard (pronounced buhSTAHRD). Then I could all kinds of free stuff and discounts when people mispronounced it and I acted all outraged.
In Wales everybody is called Ieuan Jones (except for the people called Dafydd Evans, that’s the only other option), so people are often referred to by the name of their house or where they are from.
Ieuan Bryn Pen Glyn
Ieuan Cadwst
Ieuan Blaen y Cwm Bach
Ieuan Pant y Glyn - They all pretty much describe where the house is in relation to hill/valley/water.
And in the village the guy who had the shop was Dafydd y Siop.
So I’d like to have my house for a surname. We were often referred to that way anyway. Gracer Wern Pennant: Gracer Damp Place at the Head of the Stream. 
I would go with Gates-Buffett. Then I need a plan to show how I’m related…hmm this might need some work.
I might go with something like Volcanis because I volunteer with dogs. Of course that also makes it look like I’m from an area with volcanos, so that’s cool, too.
This is always something that kind of bothered me. Personally, I’m not a fan of last names and fortunately my first name is well known but uncommon enough that I’ve only met a handful of people with it. Also, my name has a few different diminutives, and the one I go by, I’ve never met anyone in person that uses it, though a few celebrities with my name do (which, inevitably, gets me associated with them). Nonetheless, I never introduce myself with my last name, except perhaps at something super formal like a job interview.
The reason I mention all of this is because, I think for a lot of us, or at least for me, I don’t feel like I own my last name. My father didn’t choose to give it to me, nor did his father to him. It’s just something I inherited. So, I also liked where they came from, that it arose out of some defining characteristic. I’m particularly fond of how they come about in fantasy or mythology due to something memorable that character or a recent ancestor did. Frankly, I think it would be kind of cool if we had a tradition like that. Some people have some pride in their last names, because it ties them closely to someone historically significant.
For me specifically, I’d think that this sort of new last name should be chosen a lot like a nickname. That is, a nickname that one makes up for oneself is inherently tacky and misses the point since it should be about how your peers see you. So, I think looking at various nicknames I’ve had would be a good place to start. I have long hair and I’m muscular, so I’ve had a lot of nicknames related to that, associating me with pro-wrestlers or athletes or actors or historical/mythological/fantasy characters, the current one I hear most often is Thor for obvious reasons, so I imagine that if I let others pick one for me, it’d be along those lines. But I’ve also had names relating to my character, my philosophies, temperment, interests and that sort of stuff, and since I’m not superficial at all, I’ve tended to be more fond of those and I’d prefer something along those lines, since I’d rather be known for my passion for music, my philosophy, having strong will, but the people who would call me by stuff like that are much less common.
But, that all said, if I had to pick now, I guess I could deal with some association with Thor, maybe the obvious Odinson would be best, because it also ties to Odin, who is strongly associated with Wisdom and Poetry, which would cover some strong interests of mine as well, so I’d get some of both aspects of the nicknames I’ve had.
If I am not mistaken, I believe many last names in the USA came from when the ancestors landed at Ellis Island and simply stated their first and last names.
I mention this as I once worked with a man whose last name was “Gutentag” - which is German for “Good Day” or basically, “Hello.”
I always envisioned his great, great grandfather arriving at Ellis Island, not speaking a word of English, and some bureaucrat yelling, “Last name?” and the poor guy, not understanding, simply smiling and saying, “Guten Tag.”
Wait, are you telling me the Llewellyn I used to work with was a fake? Damn!
For some reason, all us foreigners would look at that string of letters and go “uh… [to someone else]pst, how do you say this?” Turned out to be pretty easy but it always scared us at first sight.
I didn’t feel like I owned my maiden name, and it didn’t help that I didn’t particularly like it, either. After my last divorce, I decided that I would take a name I liked and that suited me, since I didn’t want my maiden name back and definitely did not want either of my ex’s last names. I pondered this quite a while and ended up choosing, of all things, my mother’s maiden name. It’s a name I’ve always liked, it’s easy for most people to spell and pronounce, but it’s still unusual enough to not be in the top 25 last names. No, it doesn’t reflect me from a geographic, employment, or hobby standpoint, but that’s okay, I still really like it.
I would choose my favorite color, because I have very little attachment to my family and no desire to be associated with them. And Rachel Cerulean has a really nice ring to it.
I don’t think “call center jockey” is a profession that lends itself well to surnaming…