So, what I am wondering, is theoretically, what is the best Gestalt Social Character that can be made. Now, by this I mean that the character should be primarily built around solving problems through a mix of stealth, creativity, and (most importantly) social skills. Ideally they would be reasonably competent in combat, but mostly they would want to solve things in a noncombat way.
Now, a couple of caveats here. Yes, I am aware that the best class for solving problems in noncombat ways is arguably the wizard. I don't want to rely on spells for everything. (though I could be persuaded to consider sorcerer on one half of the gestalt)
Second, no Empiricist Investigator or any other Int for social skills shenanigans. I don't want a character who debates his way through social situations, I want him to be genuinely charismatic.
Aside from this assume gestalt with all first party Paizo material allowed.
Some of my potential classes of interest so far have been: Bard, Mesmerist, Rogue, and maybe Sorcerer.
Unchained Rogue, Phantom Thief
Bard, Archeologist or Brazen Deceiver
You killed my Vigilante (Vanilla)/Investigator (Empiricist) combination before it left the gate.
A Paladin/Court Bard would be my suggestion. The bard gives the character most of the social skills and versatile performance (Sing) gives him a good bluff and sense motive. The fact that sense motive will be based of CHA is a huge advantage. The court bard gives him a bonus to Diplomacy equal to half his level. The bards spell list is one of the best for social situations. It also gives you heroism as second level spell. Heroism may not seem like much, but it is a long lasting buff that affects almost everything. Mockery allows you to impose a penalty to your opponents CHA checks and CHA based skills.
The paladin gives you a lot of useful abilities but more importantly people tend to trust paladins. When a paladin tells you something a lot of people tend to listen. They usually have very good reputations and people are willing to trust them. Their aura’s give anyone near them bonus to some saves that are going to be important in social settings. The fact that they are immune to fear and later charm also gives them a big advantage.
For race go for human and take the alternative racial traits focused study and silver tongued. Use the first skill focus for perform sing and the second one for diplomacy. If skill unlocks are available take signature skill diplomacy. At 10th level you will have a 30+ diplomacy and can alter someone’s attitude in 1 round and shift it three categories instead of two.
The alignment restriction may be a little challenging but it can be done.
Also look at taking the Natural Charmer feat if you can, probably through Racial Heritage. The ability to Take 20 when talking to the king cannot be underestimated!
Bard also gains access to the Glibness Spell, which is also mind-bogglingly good. You can also gain it through the Bracers of the Glib Entertainer item.
Eldritch Heritage with the Rakshasa Bloodline (or just a Rakshasa Sorcerer) is also very helpful for its anti-lie detection and other benefits :)
Other then that, a Mesmerist can be a great vehicle to build the Ultimate Mind-Manipulator.
Stealth and social skills? I'd start with a ninja (stealth=yes) and gestalt it with a psychic searcher oracle. Psychic searcher gives you inspiration to push those skills higher and the intrigue mystery has revelations you'll want. The song-bound, legalistc or aboleth oracle curses could help; remember that oracle 'curses' are thinly disguised benefits.
As long as your ki holds out a ninja can be competent in combat. That's not forever of course.
Rogue/Ninja/Spy for class abilities and 8+int, Int-based Spellcaster for spells: Wizard, Witch or Arcanist.