If my feeble mind is working, I can think of winners with quads to be Kulic, Stoiko, Plushenko, Yagudin, Lambiel, Lysecek, Takahashi, Verner. Of course, there was Browning prior to 2000 but he did Win!
The morals of this story are:
a. If you're going to fall on the quad, the rest of your program better be up to snuff: high levels, positive GOE, and great PCS. In short, a great all-around skater. It seems this happened once in a major championship -- Buttle's bronze at Turin.
b. If you've got quads in your program, you can't underrotate them, and you better not make a mess of the rest of your jumps.
c. Even with a quad, you better be in the running for top PCS. At Turin, not only did Chengjiang Li land a 4T+3T, he got the higher GOE than Plushenko, who did 4T+3T+2Lo, as did Lambiel, who go the same GOE as Li.
2005 Worlds was an anomaly with Plushenko's withdrawal, and Joubert's meltdown in the LP.
To take a look at the 2006-7 season, the only skaters to win a GP, Euro, or World title without needing a quad were
1. Brian Joubert, who landed quads at TEB, CoR, and GPF, but was so far ahead of the field (Preaubert at TEB, Weir at CoR, and Takahashi at GPF) that he didn't need them all to win, perhaps because of the quads he landed in the SP's
2. Evan Lysacek, at CoC, in a weak field. Second-place Davydov didn't have one either.
3. Oda, in a middling field at Skate America
Lambiel, after a disastrous SP at Skate Canada, needed his quad in the LP to beat a quadless Takahashi for gold. Takahashi needed his at NHK to beat a quadless Oda.
Sandhu needed the quad to eek out the bronze over Scott Smith by a little over a point at CoC, and Klimkin needed a quad at CoR to beat out Verner for the bronze.
2007 World Championships (including number of quads in the LP):
Joubert -1
Takahashi-1
Lambiel-2
Verner-2
Lysacek-1
Sixth-place Buttle underrotated his. The only other skaters to attempt a quad were Preaubert (11), Sandhu (16), and Lutai (18).
2007 European Championships:
Joubert-Y
Verner-Y
Van der Perren-Y
Davydov-N, which lost him a bronze medal in a squeaker, less than a point
Lutai-Y
Preaubert-Y.
The only other skaters to attempt a quad were Ponsero (13), and Griazev, whose attempt was downgraded.
2006 Olympic Games, where half of the men attempted at least one quad:
Plushenko-Y
Lambiel-Y
Buttle-Y, but fell
Lysacek-N
Weir-N
Joubert-Y, but four major jump mistakes
In addition, Van der Perren, Klimkin, Zhang, Li, Sandhu, Verner, Dambier, and Lindemann got credit for at least rotating the quad, but had problems and lower levels in their programs.
2006 Worlds:
Lambiel-2
Joubert-2
Lysacek-1
Oda-N
Sandhu-1 (4th in the LP, making top four with quads)
Buttle-N
In addition to these skaters, Weir landed a flawed quad (got 7 points for it), but had two other major jump failures and two L-1 spins, Klimkin had a good 4T sequence, but generally lower levels and content, Min Zhang had two quads, but errors and low rest of program content, Verner had an up-and-down program, Chengjiang Li had a mess of a program, and Dinev landed one

rock) but had only a couple of +GOE elements and only okay PCS.
2006 Europeans
Plushenko-1
Lambiel-2
Joubert-1
Dambier-1
Klimkin-1
Preaubert-N
In addition to these skaters, Van der Perren (7th) had a quad, but other jumping errors, Verner (14) had a fall on his and two other jumps.
2005 Worlds
Lambiel-2
Buttle-N
Lysacek-N
Weir-N
Li-Y
Joubert-Y
Sandhu, 3rd in the LP, had one, but he was too far behind after the SP. Without it, he barely would have made top 10. Li would never have been in 7th after the LP and 5th for the competition without his two quads: his levels were 1 and 2, and he had three jumping errors and a 1A. Joubert fell on his quad, and was a mess for the rest of his program. (He would have been lower than 13th had he not had great PCS.) He would not have been seeded had he not landed a quad combo in the SP.
Plushenko fell on his quad combo in the SP, before he had to withdraw. A slighly healther Plushenko would likely have made the podium with at least one quad.
Below them, Dambier couldn't make up low levels and a doubled loop with one quad, nor could Lindemann, even with a +1.14 GOE on his opening 4T+3T, but also a fall, low spins levels, and a 1A. Goebel couldn't either, with two falls, one on the quad. Min Zhang had two quad/double combinations, to no avail, with all L1's and a 1A. Pretty much all Griazev had was a quad (another 1.14 GOE).
2005 Euros:
Plushenko-Y
Joubert-Y
Lindemann-Y
Lambiel-Y
Griazev-Y, and despite low levels and a 1F ended in 5th in the LP and competition.
Van der Perren-N
Dambier, 4th in the LP after the podium finishers, had one.
Lezin had one, but all L1's, lots of other problems, and 5's in PCS.
There were no protocols for Euros, Worlds, and Olympics before 2005. From what I remember:
2004 Worlds:
Plushenko-Y
Joubert-Y
Lindemann-Y
Lambiel-Y
Weir-N
Weiss-I think a double-foot
IIRC, Sandhu, after blowing the SP, Li, and Zhang at least had attempts.
2004 Euros
Joubert-Y
Plushenko-Y
Klimkin-IIRC, an attempt at least, plus the 4T in the SP in Swan Lake
Dambier-4S
Lindemann-can't remember, but he was doing the attempt regularly then
Lambiel-same as Lindemann
2003 Worlds
Plushenko-Y
Goebel-Y
Honda-Y
Li-Y
Weiss-two-footed attempt, I think
Joubert-probably
I'm fairly certain Griazev tried. I don't remember about Vlascenko, but I think that was the year he did a Bobrin program to "Die Zirkusprinzessin" that I really loved. The other likely suspects were Zhang, Sandhu, Dinev, I think Jeannette. That was early Lambiel, and I can't remember if tried quads as early as that year.
2003 Europeans--the ISU link is broken and I couldn't find a results list (although I did find a newsletter which celebrated "1,500 happy new residents of Malmo!"
Plushenko-Y
Joubert-Y
Jeannette-I think so.
2002 Worlds:
Yagudin-Y
Goebel-Y
Honda-I think so
Abt-probably
Li-almost always
Weiss
Of the others, probably Zhang. Don't know who else.
2002 Europeans (another missing page)
Yagudin-Y
Abt-Y
Joubert-maybe. He was a baby then.
2002 Olympics:
Yagudin-Y
Plushenko-Y
Goebel-Y
Honda-probably
Abt-probably
Eldredge-N
Others who might have: Stojko, Li, Dinev, Zhang
2001 Worlds:
Plushenko-Y
Yagudin-Y
Eldredge-N
Goebel-he had at least a quad by then, no?
Honda-probably
Yunfei Li-I remember liking him, but I don't know if he had a quad.
2001 Europeans:
Plushenko-Y
Yagudin-Y
Jeannette-I think so
Abt-most likely
Davydov--I don't think so
Vlascenko-possibly
2000 Worlds
Yagudin-Y
Stojko-Y
Weiss--did he attempt?
Plushenko-Y
Li-Y
Abt-maybe
2000 Europeans-can't find any links.
Since Worlds 2000, there hasn't been a World, European, or Olympic Men's champion without the quad -- and at the Olympics, 1998 with Kulik and did Urmanov land one in 1994? -- only one silver medallist who likely would have won bronze had Plushenko not been injured (which may have psyched Brian Joubert off the podium), and a few bronze medallists. Under either system.