Lincoln wanted a War Democrat VP, as has been said in this thread.
William Rosecrans was considered for VP in 1864 and was in communication with the administration. However, his telegramm that he sent indicating his interest in the position was intercepted by War Secretary Edwin Stanton (who did not like Rosecrans much) and thus it went to Johnson.
Rosecrans as President instead of Johnson would be interesting. He'd also likely not get any nomination in 1868, considering he was a catholic.
I have heard that Benjamin Butler was also considered as VP in 1864. He wasn't very good as a general, but he seems to have been fairly skilled as a politician, so that could be a win/win situation.