This is definitely a tough one!
It seems like I've been there a number of times, my "genealogical brother", and I have to believe that it IS solvable - it's just not far enough back in time to be impossible. The keys are (1) perseverance above all, (2) what I call "real work", which means not relying on flawed indices and records being conveniently available online and (3) sometimes a little luck helps too.
I'm reminded of how I found the parents for one of my own gt-gt grandparents. The family lived in Buffalo NY, but I couldn't find her in earlier records, despite having known her maiden name. It was actually BAD information that put me in the right direction! A death certificate (probably of her son, my great-grandfather, I forget offhand) said that she was born in nearby Lancaster NY. Thing is, everything else said she was born in Ireland!
I checked out Lancaster NY, and starting to find things! Apparently the informant for the death certificate knew only that she was FROM there - which she WAS. She was born in Ireland, but moved there as a small child! They were even married there. The spelling of the family name in the census there was pretty messed up, too. So I may never have found them there at all, if not for the bad info on the death certificate.
Anyway, based on that experience, and many others, I have a number of thoughts on this difficult situation.
* Let's ask ourselves where a man from Scotland meets and marries a French girl? Well, I happen to have done some research for my nephew, whose mother had ancestors in northern VT, near the borders of both NY and Quebec.
What I learned is that the triangular region between the St Lawrence River and the US border (NY & VT), in Quebec, immediately south of Montreal, was settled by people from Scotland in the early 1800s, if I recall correctly. This being Quebec, there are French people all over the place as well. So I'm thinking your French girl may or may not have actually been born in France - I'd guess that she was simply French-Canadian.
I figure the couple migrated into neighboring VT (in the NW corner, on Lake Champlain), where William was born. They probably moved before long, and he spent most of his childhood in MI.
* The occupations I'm seeing for William are fisherman, chef, and steward. All of these can relate to the water, so maybe William spent his early adulthood working on ships on the Great Lakes. Note that his future bride is living on the western shore of Lake Michigan (one of the Great Lakes, of course) in the 1910 census, which would be JUST before they married.
* I'd guess that the two might be Catholic, so you might want to get a look at the Catholic Church records for the bride's parents' parish, back in Milwaukee (again, that's "real work"). It's also possible they married near where they met, or at the groom's church "back home" (wherever that was), or other things.The marriage record, whether civil or from the church, might tell the parents.
* "Charlton" seems like an unusual name, and appears to be Scottish, as far as I can tell, so at least that much makes sense. But it also seems like the kind of name that is just asking to be misspelled, in a variety of ways. Usually when people show up missing from the records a lot, it's because of handwriting/spelling/transcription errors (it's especially bad with some German names). In your case, they may have also been in Canada at times.
* Other things can happen to mess things up. For example, if William's father died, and his mom remarried, he might appear in the census under his step-dad's surname!
* Analyze the heck out of your DNA matches - their Shared Matches are essential. Chances are, you have a number of distant relatives on that side in your matches, and they might provide the clues you need to get there! If anything, you should always work out your distant relatives on that side, because you never know whether something will pop up regarding those relatives that will give you a clue to the ancestors.
* Good luck!
