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.
This answer is based on two play-throughs of the scenario, on Emperor difficulty, as the Almohads (Muslim) and the Russians (Eastern Orthodox), to pick up their respective Steam badges. I won both times, with occasional help from minor save-scumming. In general, winning takes around 3000-4000 victory points.
Sources of Scenario Victory Points
Your best, most repeatable, (almost) always available, and reliable source of victory points is conquering cities from other religions. All other sources of victory points are useful, but can't give you the victory with that alone: Holy Roman Emperor elections, Caravels sent to the New World, and holding a Holy City can, each, only give you roughly half of the required victory points.
Conquering cities from other religions
Conquering other religions is a huge source of victory points, especially considering that humans are better at war in Civ V than the AI is. (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, or about 10% of the points you need to win. You will, of course, be burning several cities; there just isn't enough happiness in the world for you to puppet or annex everyone, even if there are new luxury goods from the G&K expansion. If you're going to 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.
Holy Roman Emperor elections
Becoming the Holy Roman Emperor requires a fair number of city-state allies; I don't pursue these victory points, but the AIs usually have 5 or 6 votes when they win the election, so you should have 4 or more city-state allies if you want to be elected. I find it difficult to compete with 10 different Emperor-level AIs for the love and adoration of city-states, so I ignore them and thus the Holy Roman Emperor elections. (On Emperor, I won't have the most culture/faith/science, and I won't have money to spare for bribery; the only cheap-and-reliable city-state quests are great people, barbarians, roads, and religion. Roads and religion are one-shot bonuses to influence, great people spawn quite slowly, and barbarians are pretty rare once the game gets going - the map is too crowded to spawn them.)
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). I recommend conquering over allying; on the harder difficulty levels, you will not have more money than the various AIs, and they can easily bribe the Holy Cities out from under you.
Sending caravels to the New World
On moderate and low difficulties, you can out-science your rivals and produce Caravels without jeopardizing your military technology too much. On the higher difficulties, your rivals will all produce more science than you, and you simply cannot afford to fall behind in the march towards cannons and other high-tech units. In ideal circumstances, you can generate 1500 victory points with Caravels; this is about half of a victory, but you must have at least one other way of earning victory points.
Other notes on the scenario
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.
A word on religion: try to get one Catholic city so you can spend faith on units, since you'll be at war a lot.
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.
One specific note about Russia: Moscow is in an awful position. Your closest neighbor is the Mongols to the east; they have no religion, so going to war with them will not generate any victory points. You should send your second and further settlers far southwest, so that they can be adjacent to Austria and other Catholic nations. In my game with the Russians, I eventually lost Moscow to the Mongols because resisting their invasion would take too long, and I had better (victory-point-producing) things to do with my turns and armies. You might consider moving far to the southwest before founding Moscow; you'll lose several turns of first-city-production, but your capital will be much closer to Russia's main source of victory points: nations of other religions.
For some Steam Achievements, you'll need to win on Deity (e.g. Mehmet the Conqueror). Even on Emperor it's quite hard already.
I can only agree to the rough guidelines stated above. By now I've won this scenario on Deity with 5 Civilizations plus Russia on Emperor. Some things I might add here regarding combat:
- bring workers to the battlefield -> have them build roads (and remove them later) so your troops have improved mobility and you can evacuate veterans quickly and bring in reinforcements
- protect your veterans at all costs!!! especially in the end game the AI amasses hundreds of units and you can't outproduce them. the only way to defeat them is with your veterans: Some "tanks" - highly promoted melees drawing fire and surviving, and a lot of highly promoted Crossbowmen (shoot 2x per turn, 3 range, bonus against all terrain etc.)
To keep your empire happy - stop city growth! Every city is only allowed to grow to it's own local happiness cap. If that is 4 - stop city growth at size 4. This is the only way you can use your "surplus" happiness to support your conquests without getting the -30% unhappiness combat penalty!
To read more general Into the Renaissance scenario advice, check out -> http://www.kalle-online.net/blog/civilization-5-renaissance-scenario-strategy-achievement-guide/