Multi-classing
As others have stated, the only classes that currently get a skill proficiency by multi-classing are a Bard, Ranger, or Rogue. Even if you focus exclusively on one of these classes, it will start with more than most characters.
As noted by T.J.L. in comments here, the Knowledge Domain allows Clerics to get extra skill proficiencies as well.
Feat
A very powerful feat, in my opinion, is Skilled. 3 skills for the cost of 2 ability points is a very fair trade when you consider attribute caps and the bonus you get out of 3 skills.
Race
A couple of races get a free skill in some form, but humans also get a free feat (see above). This means that a variant human gets a total of 4 bonus skills if you take Skilled as your bonus feat.
A second-place option is the Half-Elf. They get two skill proficiencies. Not as much as a Human with the Skilled feat, but more than a human without it.
Minor Houseruling
According to the rules (PHB pg. 187), you can train in the proficiency of a tool or a language by spending 1 gold per day of downtime for 250 days of downtime to train that proficiency.
Technically, skills aren't allowed on that list, but talking to your DM might not hurt. Although there is nothing specifically referencing skills in this regard, it wouldn't seem out of place or inappropriate to use this system for skills as well. Many, if not most, games will not allow enough downtime for frequent proficiency training (likely only 1 proficiency in most cases). Even if a DM allowed this as a minor houseruling, it is unlikely to come up often.
Synopsis
Your best bet to start a true skill-monkey that can tackle multiple roles in the way you stated from level one is to make them a variant human, and make "Skilled" the extra feat. This is a completely legitimate build, and most DM's will likely allow variant humans since they are directly in the PHB and Basic Rules.
This would give you 10 skills (4 class, 4 race, 2 background) to work with, making you very feasible as a jack of all trades spy-like character, a paragon of skills and expertise. The 4 skills from race/racial feat can be from any source as well, giving you a lot of versatility to work with.
If you want to focus after level 1, then picking up the Skilled feat is a great path to look at.
Also, you can look in to multi-classing as a bard. It does give a skill, and skill expertise, and a bard/rogue fits the Face/Infiltrator Spy trope of characters like James Bond. Although Ranger can give you another one, a 17 Rogue (Assassin)/3 Bard (Lore) is very solid and the one skill point is not worth losing a major ability as a Rogue. This character, when they hit Rogue 1/Bard 3, would have 14 (4 starting class, 4 race, 2 background, 1 Bard, 3 Bard(Lore) bonus) skill proficiencies, not even considering tool proficiencies.
Should you do it?
Depends on the group. Generally speaking, a single player shouldn't have all the skills, and the ability to have all the Player Characters rely on each other makes for a better game. Unless your group, for some reason, is very low on diverse skill selection, you may want to run this type of character concept by both your DM and the other players before creating this character.