1872 is easy: just have Grant commit some unspeakable act, and have the Democrats pick a war candidate, like Winfield Hancock - he had great popularity, a wound to his name, and had enough political clot to be Dem. nominee a few cycles later in OTL.
For 1868: you need a big split between the Radical Republicans and the Moderates, and get Grant associated with the radicals (this could be the logical outgrowth of Johnson's impeachment), but beyond that you need a very unifying Democratic candidate, who probably was not forthcoming, and then you need a WHOLE lot of luck, and a reverse-1864, with an extremely moderate-to-republican democrat, a big problem for black voters in the former CSA, and then with a whole lot of luck, you just might slip the Democratic candidate through by a few electoral votes.