This is likely unbalanced
For your tiefling paladin, this is likely at least a +3 to AC, which, depending on their build, could give them 21 AC at level 4 (shield + chain mail from Paladin starting gear, +3 base CHA modifier.) This is quite powerful relative to other options, and will improve with any additional ASI.
If this doesn't look that powerful to you, consider that +3 magic armor is considered legendary rarity in 5th edition. The bounded accuracy built into the game design means that this sort of scaling bonus to AC is disproportionately strong compared to what you would expect.
A good way to confirm this is to look at how existing features deal with this type of design. Typically, this type of thing takes the form not of a bonus to AC, but a new way to calculate it. This way, bonuses do not stack, but instead provide different possible builds with pros and cons. For the rules behind this, see this question, regarding Natural Armor and Unarmored Defense.
If you'd like to keep the flavor of this feat while making it more aligned with the balance used for player characters, consider defining a new AC calculation entirely. For an example of this in the form of a feat, see the Dragon Hide feat from Xanathar's Guide to Everything. One of its benefits is the following:
While you aren't wearing armor, you can calculate your AC as 13 + your Dexterity Modifier. You can use a shield and still gain this benefit.
You might template something similar, using Dexterity and Charisma. The exact numbers would be a matter of experimentation and testing to see what seems balanced for you. The key point, though, is that AC increases shouldn't typically be strict improvements over armor, but rather an additional option different from armor.
Naturally, the rules are different for monsters like the cambion, which get to break these norms.
For completeness, I should make note of the warforged case. In the playtest version of the warforged race (found here,) the warforged Integrated Protection feature allowed them to add their proficiency bonus to their armor class. This is similar to what you'd get from using Charisma (a bit lower at early levels, a bit higher later on.)
In the published version, in Eberron: Rising from the Last War, the AC bonus was reduced to a flat +1. One could interpret this as the playtest material revealing that a scaling bonus to AC was too strong, resulting in an eventual reduction in the feature's power.