Could you take out a civilization before it starts by killing its starting settlers and warriors? On a duel map, could you do this and win without founding your capital either?
tl;dr: yes, you can do this, although it makes the game a bit confused.
This question made me curious, so I tried Affine's strategy of putting 22 civs and 41 city-states on the smallest possible map size. The game assigned me the Shoshone civ, which turned out to be perfect: their cities start with extra tiles, and they have a unique unit — the Pathfinder — that acts like (and replaces) the Scout but has the combat strength of a Warrior. Starting the game as the Shoshone, you get a Settler and a Pathfinder instead of the usual Settler and Warrior combo.
On my first turn, I founded a city, and its borders shoved Spain's starting units onto a little peninsula. I wasn't able to get my Pathfinder over to the Spanish Settler, but that Settler was too close to my city to found a city on its turn, and I was able to capture it on my second turn. I'm not 100% sure what happened to Spain's Warrior; it seemed like it just disappeared when I founded my city, but it could have been pushed onto a hex I couldn't see. I remained at war with Isabella for about ten turns, after which Spain just disappeared from the Diplomacy menu.
In the same game, I noticed that the Huns hadn't founded a city by turn four. I captured their Settler, but their Warrior ran away from me and the civ remained in the game. It took another four turns for me to track down that Warrior and attack it. The combat went normally; neither my Warrior nor the Hun Warrior was destroyed, though both took damage. Then, after I ended my turn, the Hun Warrior just disappeared off the map, without being attacked. When my next turn started, the Hun civ was no longer in the Diplomacy menu.
To test the second part of the question, I started a new game with the same settings, except that I had it start from the Classical Era instead of the Ancient Era. That means starting with a Settler, a Worker, a Spearman and a Pathfinder. I never founded a city. I was able to capture Venice's Settler on my first turn, and destroyed its military units over the next five turns. I didn't go after the Worker, though. It kept running around until turn 50, at which point I gave up hope that the game would consider the civ lost.
I did not have the "Complete Kills" option turned on.
Theoretically, you could. If you somehow managed to capture a civilization's starting settler(s), you could eliminate them from the game very easily.
In practice, this will effectively never happen, as virtually every civilization will found their city on the first turn, and the game's start placement logic will avoid placing civilizations close enough to manage it.
The AI will always settle their first city immediately. On higher difficulty levels they start with an extra settler so by the time you reach them you're probably going to be dealing with two cities.
In multiplayer games, if a player is going to be moving their settler before placing it, they will almost certainly protect it with their warrior (if they don't, more fool them).
And in case you're thinking of stealing that second settler for yourself, taking an enemy settler converts it into a worker (though ya know, free workers!)