The Tokugawa Shogunate was unpopular amongst certain daimyo (the same ones who revolted in the Boshin War) for the whole period, just those daimyo never revolted against them until they had the chance in the Boshin War. They possibly could have before the Meiji Restoration, in favour of another emperor (or maybe even a younger Emperor Meiji). I'm not sure when they could have revolted and defeated the Tokugawa, just they would have also needed to back whoever the Emperor was at the time in order to fulfill this AHC.
The Kenmu Restoration is obvious, but that's centuries before and pretty much something entirely different and if successful would lead to something entirely different than the Japan we know. But I think the odds were against Emperor Go-Daigo the entire time. With my knowledge of Japanese history, maybe he could have allied with some sort of peasant rebellion (like the Ikko-Ikki) and gained support over the warrior nobility who wanted to keep the status quo at the time. But Go-Daigo also strikes me as a fairly arrogant person, so you probably would have needed a different Go-Daigo for him to succeed in his Kenmu Restoration.