Hint #3: Lincoln was in Harpers Ferry, WV, on October 1, 1862, on his way to see McClellan at Antietam. West Virginia did not actually become a state until June 20, 1863, but I am counting the Harpers Ferry visit as being in West Virginia.
Hint #4: The one where I thought I would get a debate was Tennessee. Lincoln made flatboat trips down the Mississippi River to New Orleans in 1828 and 1831, and I think it can be logically assumed he stepped ashore on the Tennessee banks during both those trips.