Well the first question is, when would *Twain need to go into politics, and how much would he then resemble the man OTL knew?
Let's see if we can find that out working backwards -- Clemens was born 1835, and the average Presidential age is around 55, so we're looking at becoming President around 1888 or 1892; the earliest he could constitutionally be elected either President or Vice-President is 1872, and can't realistically be elected after 1900 (at age 65). While he'd essentially have to first be elected as Governor or appointed Senator of some state first, there's little no real minimum time of service required for either office, so it can be as little as two years prior; the trick is, since he never became a lawyer OTL, to either find a way to make him realistic candidate for one of these offices without, or else change his early life so he becomes a lawyer instead of a journalist/writer.
And that brings us to the next question -- which state should he start his political career in? What makes this tricky is Clemens was moving around so much in his early life -- Missouri, the Nevada Territory, California, New York, Conneticut -- and he'd have to be settled in one location long enough to be considered "local" (at least legally enough) to run for office. That said, if you want the Twain of OTL's liberal views, you really can't do anything to stop his 1870 marriage to Olivia Langdon in New York (her abolitionist family had a great deal of influence on him). Currently, residency requirements for running for the NY State Legislature are five years.
Therefore, one thing I'd start with for this TL is to stop *Twain from moving his family to Connecticut in 1871. From there, you just need to find, with no PoDs before this 1870-71 period, a way to get him involved in New York politics, so that he's a plausible candidate for Senator or Governor by 1890 (or so). Good luck with that!