I've only ever won the game on King and below, and I've won at King once, although I'm almost certainly going to win in my current game.
Here's what I've figured out so far. You can breeze through the easy difficulties without any kind of serious military and without ever going to war. War is unavoidable at King and, I'd assume, above. Getting wonders is really hard.
My first 100 turns essentially go like this as far as build:
* Scout
* Monument
* Scout or Warrior/Archer
* Shrine or Worker
Research:
* Pottery
* Luxury Tech or Writing
* Construction
My goal is to have 4-5 archers build with enough bank to upgrade them all once I hit construction, because if war were not already declared by then, it soon will be. I also get to get down 3-5 cities, and I usually make my second city my "science" city. My first city is usually production/military and second is usually science, third is money, fourth is a mix. I don't usually do a culture or faith-centric city at all.
For faith, I approach it once of these ways:
* Play a faith civ, mainly the Celts and restart unless I can get the +2 faith bonus
* Find a faith wonder and build a city near it
* Find a faith CS and barbslaughter my way into their good graces
* Build Stonehenge
If I can't do one of these, I wait until I have 4 cities and put shrines in all of them and found a late religion. I try to get 1 shrine up in my cap early so I have a shot at a decent pantheon bonus (I almost always take +10% growth unless the situation makes something else more appealing). I basically use religion for happiness and little else.
I'm usually REALLY late to get libarries and national college up, I tend to expand quickly and build up a military and usually don't do library/college until after my first war, which puts me about 3-4 techs behind the AI. I usually close that gap by turn 200. I'm sure that won't work at higher difficulty levels.
For social policies, I usually open with liberty for the settler and worker and use the GP to pop an engineer and use that to build Notre Dame if I can get to it in time (50/50 chance) or pop NC if my science city has lousy production (it usually does) just to get that going quickly.
One thing I have noticed is that if I'm not balls-out trying to get wonders, the AI usally isn't either. I've got a game in the 19th century and nobody has build the Pyramids yet.
If I get Stonehenge, it'll be in my capital and that usually means a second engineer, which I use situationally. If I do get SH, I'll usually try to pick up one more +Eng wonder, like Pyramids or Artemis. I like Artemis because the archer build bonus dovetails with my archerspam defensive strategy. With a few roads and 5 compound bowmen you can hold off basically anybody.
I also like honor, and go down the right side first. I use the garrison bonus to get +hap and +culture and I spam walls and castles and everything else - they are 0 maintenance, so it's free happiness, and I need them anyway. I usually go rational next and the game is almost always over before I finish it.
What I'm learning is that an early war is critical. I basically wait for the DOW, move units it, beat back the opponent, and then take their capital, which usually has 2-3 wonders by then, then recover, build up cities for research, my goal is usually to have NC built before the second war (rarely happens), universities before the third, then get to public schools, etc, etc.
I kind of fall apart as far as direction after I get education. I usually head for rifles and cannons and then flight and build a ton of bombers but I kind of lose focus after that and just do whatever. Victory is inevitable at that point usually.