What are the key concepts to grasp, or a winning strategy, for the "into the renaissance" (faith based) scenario?
I don't have a ton of experience with this scenario, but from what I've experienced so far, the key is the city states.
I played as France, which gives you a bunch of culture at the beginning of the game. I used this to push the Liberty tree immediately, getting a third settler and extra/faster workers. Since each settler turns into a size 3 city, its important to grow early on, and there are plenty of luxury resources to keep happiness from being an issue. The game may play quite differently for powers in different parts of the world, so consider this guide to be primarily for western Catholic powers.
Once I had my starting cities down, I focused on city state relations. Obviously this means that you need to make exploring an early priority, so that you can meet as many city states as possible. Once you meet a city state, you should start getting rapid fire quests from them. These quests often overlap, so you can gain relationship with several of them at once. Keep enough of an army so that you can take out barbarian camps as needed. By the time the first vote occurred, I received 9 votes, and I only had to use money to boost relationships twice.
In terms of faith, I started out by focusing on cathedrals to boost my faith (and culture) output. You don't really need the units early on, and you should be able to start accumulating faith quite quickly by befriending some religious city states. Once you have the faith rolling in from all your friends, you can use it to build up an army that should keep any aggressive neighbors at bay.
Not only does helping the city states give you tons of bonuses at a relatively low cost, but if you can secure Vatican City, you should rack up the victory points without much issue, between the Roman Catholic Emperor vote and the bonus points for being allied with a holy city. I ignored Jerusalem, since it was quickly conquered by the Turks anyway.
I've found victory easiest by conquering cities from a different religion. (Die, heretic!) At 25 victory points per unit of population, a size-16 city (such as you see in the mid- to late-game) will grant 400 victory points; since winning takes around 3000-4000 victory points, this is a sizable chunk. I ignore city-states (and hence the Holy Roman Emperor elections) and focus on conquering people from a different religion. I've won on Emperor twice now on Into The Renaissance (as the Almohads (Muslim) and the Russians (Eastern Orthodox), to pick up the Steam badges). On that difficulty level, I find it hard to get enough money to bribe city-states compared to my computer opponents, though quests are still a decent way to get allies.
If you can pick up your holy-city-of-choice and/or Jerusalem, by allying or conquering, it's very much worth it (10 points per turn * 200 turns = half a victory), but you can win without taking any holy city if you conquer enough people. You will, of course, be burning several cities; there just isn't enough happiness in the world for you to puppet everyone, even if there are new luxury goods out there.
Note that the Byzantine Empire is your biggest rival; if you don't win, they usually will. They will have a holy city for the entire game, and they're surrounded by opposing religions: their neighbors are either Muslims or Catholics, so any city they take will give them bonus points. If you're going to take my advice and crush your neighbors in the name of your religion, it is very important that at least one of your immediate neighbors is not your religion. This makes most of the Catholic powers poor starting choices, since they're mostly surrounded by other Catholics.
A word on religion: try to get one Catholic city so you can spend faith on units.
The Random Europe map is, I've found, easier to play than the historical map. Some of the bottlenecks from the historical map are wider in the random map. Also, the locations of the city-states are randomized on the Random map; Jerusalem, Mecca, and Vatican City can be almost anywhere. This can make it easier to win with some of the more remote European powers such as the Celts or British.
Given the high cost of Settlers, it is very much worth it to take the Liberty culture tree at least as far as the free Settler.