So, here's my approach:
A custom skill can be bought at the cost of any 2 other skills. This includes skills a character gets as part of his class.
The custom skill must be some sort of role (sailor, soldier, blacksmith, whatever) but it must also have a setting specific context (i.e. a sailor must have sailed with a particular navy or merchant fleet or something similar). This doesn't need to be written down in the skill name (though it can be, if it's brief), it's just something the GM and player need to be aware of, both to tie the custom skill to the setting and to help answer questions of context when they come up.
This custom skill can now be used as any skill within its specific context. That is to say, that when performing shipboard tasks, the 'Sailor' custom skill can be rolled in place of Endurance, Athletics or anything else. When it comes to knowing strange lore of the sea it may be used in place of Arcana. In short, it is a superskill within that specific context1.
Now, this is in part why it's important to keep the context very clear. Without boundaries, it is entirely possible to make custom skills overwhelming, especially if you treat it as just geography. It is not that a sailor can use his Sailor skill for EVERY activity on a ship, just the ones that sailor's do. Thus, he might be able to use sailor as a perception base to spot what's wrong with a ship, but not to spot ninjas sneaking aboard a ship.
Still, this is easily addressed with clear communication, and because this system mostly works within the context of existing skills, it's minimally disruptive while still expanding the scope of what can be done beyond the existing list.
That said, here are some optional rules:
If a custom skill seems too broad but not broken, it might be purchasable for 3 skill slots.
A less potent version of this approach swaps in custom skills for a single skill. In this system, you roll the new skill when no other skill is appropriate, but if you roll a real skill instead, you gain a +2 to the roll2. If you use this rule, you can replace the racial skill bonuses with a racial lore skill which implicitly covers those bonuses and which also allows for knowledge of what Tieflings enjoy for breakfast (and, implicitly, make those skills available to people outside the race)
The least potent version is simply "Works like a skill when no actual skill exists". In this case, I would not charge for it, but instead give each character one for free as part of the background system.
Hope that helps.
1. Structurally, the skill provides the capability to perform actions, knowledge about the topic, and a certain amount of awareness about relevant data.
2 - I forget the bonus type, but it doesn't self-stack.