Actually, here's two more riffs on the stone sorcerer crunch:
1. You are the reincarnation / spiritual descendant / actual descendant / host body of a great warrior. You may not have the physical gifts of some fighters (having pumped up that Charisma stat), but you literally have a warrior's spirit, making you a natural leader who can instinctively wield any weapon like a professional and can channel strange magics through your sword. Great angle for an unlikely hero --- the local scribe's apprentice or baker boy finds out he is the heir to Kogarth the Unyielding.
2. Marry this to the Inheritor background --- you inherited a magic sword. Its magic will increase over time (does 5E do scaling magic items yet?), but it's also awakening your own powers. Could be another unlikely-hero-call-to-adventure kinda guy, or it could be a Stormbringer-type curse --- you are gaining in power by killing.