I'm usually more of a lurker, but here goes...
I think the game will be hard enough on Immortal and Deity, but this is primarily because the AI has a huge advantage in some specific areas of the game, such as war. They not only get a +8 combat strength bonus on Deity, they seem to have a much easier time getting war support (I'm not sure if they have a bonus towards spending influence on it, or just get more influence in general), which leads to you getting war weariness and significant combat strength penalties. If you end up fighting multiple wars, with multiple AI's boosting their war support, this can get out of hand really fast (your combat penalty can reach -10 or even -20, while they have a +8 bonus). But I'm sure people will find a way around that. It does make influence a pretty important resource for war though.
With that said, I've seen the AI do plenty of really stupid things, like leaving their army commander undefended and easily killed (and army commanders, especially experienced ones, are super valuable).
Speaking of bonuses, one thing I did like was that the AI didn't seem to start with extra settlers on Deity. At least in the Deity games I tried, the AI's I met right at the start, didn't get their first town / second city until like, turn 20 on standard speed (you can tell from their military milestone points), which is roughly when you can get yours as well. So that's a big positive, at least from my point of view. But that's not to say they don't get major bonuses to other things on Deity, they do (like in the example above).
As for befriending the "barbarians", I did focus pretty heavily on getting more influence, specifically with that goal in mind, and I picked up some attribute bonuses that make it easier as well (and as mentioned above, influence can be a very important war resource due to the fact you can use it to boost war support at the start of the war, which gives a direct combat advantage). That's just one strategy, I'm sure there will be many others.
The aggressive editing was sadly necessary, because we were limited to one hour only. I definitely had to cut out more than I wanted to in order to fit in that one hour limit...
Edit: Oh, and the city cap is more of a soft cap than a hard cap, you just get -5 happiness penalty for exceeding it (for each extra town/city over the cap, up to -35). So exceeding it by one or two is not that big of a deal, there are many ways to boost happiness. The biggest pitfall of doing that is the crisis that tanks your happiness (there's more than one crisis type, so there's some randomness in which one you get) - if that happens and you fail to get it back into the positives quickly enough, the city will flip to the the AI. Speaking of the crisis, it can also be turned off during game setup.
Edit 2: One more thing I want to say is that I played through the whole antiquity age on Deity and standard speed, and it felt easier than Deity in Civ 4 or Civ 5. I found the happiness crisis to be more challenging. BUT this is a very small sample size, so take it with a grain of salt. (and I haven't tried deity beyond antiquity age yet)