This is rather impossible to determine, there are numerous people that have had a tremendous influence and success on the game. While Rockne revolutionized the forward pass and won a whopping 88.1% of his games (105-12-5), I wouldn't call him the best coach ever, and while Paterno has won the most games, I wouldn't say he's the best ever either.
Some names I'd throw out there:
Frank Leahy, Boston College/Notre Dame

He only coached thirteen season, two with Boston College and eleven with Notre Dame. He went 107-13-9 throughout his career. That's an average of 8.2-1-.7 every season. Rather remarkable considering he played fantastic Army and Navy teams. Oh yeah, he won four national championships and had another four undefeated seasons that didn't result in championships. Truly a legend.
Tom Osborne, Nebraksa

He gets my vote for the best coach ever. If success was measured by consistency, he'd take the cake. His teams never won
less than nine games in a season. He won thirteen conference championships and three national championship in his 25-year career. His lowest finish
ever, to end a season, was 24. That's just remarkable. He finished 255–49–3, not too shabby.
Paul "Bear" Bryant, Maryland/Kentucky/Texas A&M/Alabama

In 38 seasons he was 323–85–17. He won fifteen conference championships, and, depending on who you ask, won seven national championships. Whereas Frank Leahy dominated the 1940's and Tom Osbourne dominated the 1990's , Bear Bryant the 1970's. He won five AP national champions, has anyone won more? However, he never beat Notre Dame.