Sorry for the bump, but I was thinking about this again.
I'm not going to include those mentioned already...
1812 - Madison and DeWitt Clinton.
1844 - Polk and Henry Clay.
1884 - Cleveland and James G. Blaine
1916 - Wilson and Charles Evans Hughes
1920 - Harding and James M. Cox
1924 - Coolidge, John W. Davis and Robert M. LaFollette
I consider Hoover's WWI work as military service.
That's it as far as I can tell.
Polk and Madison were in the military.
To Mr. Modern: Ron Paul was in the military, if you think he has a chance/will run.