How are poisons discovered? Does someone have to die/be poisoned from it first?
Alle Dinge sind Gift, und nichts ist ohne Gift, allein die Dosis macht dass ein Ding kein Gift ist (The dose makes the poison) - Paracelsus



Poisons (I'm going to use this as an umbrella term for "toxins" and "venom" as well. Bear in mind though, they are not the same thing) have been known since antiquity. 

Back in the good old days, you figured out if something was poisonous or not by eating/touching it (or getting someone else to do it), i.e- "discovering" a poison was simply a matter of chance.

These chance encounters alone, led to the discovery of numerous poisons.

With the advent of Chemistry, the gents in white lab-coats figured out that compounds that bear resemblance to the already well-known poisons, in terms of their functional groups and structures, are also toxic (albeit, to vastly different degrees). Poisons could now be identified a priori (you could tell it would end badly if you were exposed to such a substance, but not how badly).

And no, you can't really quantify a poison's effects without testing it on something. Nor can you tell how much of something would be needed to kill or severely maim. 

This is where we bring in the idea of a median lethal dose $\pu{LD_{50}}$ which is, simply put, the minimum amount of a substance required to kill off half of all the animals in a particular test group.

$\pu{LD_{50}}$ values for a particular substance depend on the animal used.

Of course, the only way to get an accurate $\pu{LD_{50}}$ (which itself, is really a "mean/average" value of sorts) for a human is to actually poison someone, which doesn't sound very nice. So you do the next best thing, you measure it for a rat/chimp, couple it with your knowledge of the poison's mechanism of action, and extrapolate the value to something that would kill a person.

Another way to establish degree of toxicity, which doesn't involve killing animals, would be by exposing a cell/tissue culture (and not the entire animal) to the potential poison .