Bill Snyder is probably the best example out there. In 1988 Kansas State finished 0-11 under Stan Parish. Snyder took over the next year. He went 1-10 in year one, but by year three he finished 7-4, good enough for 4th in the Big Eight. Then in 1998 his team, lead by QB Michael Bishop, lost the Big XII title in TX A&M in 2OT, costing them a chance at the NC, and finished 11-2, losing their bowl game.
In 1988, I remember Kansas' only win that year was over K-State (Glen Mason was their coach). SI did an article on the two most hapless programs in the country at the time!
While, Kansas' football history has been up and down over the decades, Mark Mangino is another, more recent example of a coach who took over a deflated program, going 2-10 in year one (2002), and brought them to the top of CF, going 12-1 in 2007, winning the Orange Bowl. That team lost to hated rival Mizzou when the teams were ranked (amazingly) #2 and #3, which cost KU a shot at NC run. (Mizzou's shot at the NC was torched the next week in the Big XII title by OU.)