1.) The situation looked bleak (even by your own starting assessment). What do you think was the turning point(s) that allowed you to start dominating militarily?
Well, it is interesting that you think I am dominating militarily. I do not feel Japan has reached that point yet. Even now Japan's military is weak compared to China. At some point Japan will have to weaken China. If that succeeds and Japan has control of the continent, then I would say Japan is dominating militarily.
There were several key points that allowed Japan to stay in the game.
First - The political situation was still fairly good when I picked up the game. Without that there was little hope of getting techs, keeping the AI dogpile off Japan, and making one civ the rogue state. Remember Japan spent a lot of time building infrastructure early on, trying to make the best of the territory she had.
Second - AI stupidity. This is not a turning point, but it is a necessary factor in this comeback. Why did Russia not declare war on me when I built a city on my territory border and took her ivory resource? Why did the Germans not declare war when I did the same thing to them to take a coal resource? Why did the Chinese AI burn the Russian city near all those furs? I used no offensive units to acquire any of these things, just took advantage of AI stupidity. Why did Germany declare war on Russia, France, America and Rome when they were clearly stronger than Japan? Surely the world map and 25 gold I gave when Germany demanded it was not enough to justify tackling a larger foe with less tactical value to their empire. Japan was small and fairly close to the German capital, it should have been an easy target. Why did America go into anarchy after war was declared on her? Why would AI players sign MPP with Japan after she had already declared war on Germany?
Third - Acquiring Replaceable Parts. Having this tech allows infantry and artillery to be built. Without artillery there is practically no hope of defeating MI with cavalry, and certainly not with the few cavalry Japan could afford to produce. Infantry allows a somewhat reasonable defense against the newer equipment. With arty Japan, backed by human strategy, had the chance to take some initiative against weakened AI civs. The MPPs were more important to defense than any unit however, as it allowed me to focus the units Japan had for defense on just one civ, not all of them.
Fourth - Acquiring oil and Computers. This allows mech inf, making defense a whole lot easier.
2.) Would it have mattered if this were a deity game?
Hmmm. Not sure how to answer this. I have limited experience at deity level. To me this felt somewhat like a deity game, since Japan was so far behind in tech and land mass. I have never been so far behind in tech and land mass as Japan was in this game. I think the game would have become dire much sooner than 590 AD at the deity level. I don¡¦t think it would have affected my strategy at all, but it would have affected the speed of the comeback and probability of success since the AI can build units much faster at deity level. The AI also gets annoyed much easier at deity, which would have affected the likelihood that one of them would have declared war on me.
Do you think you could have started warmongering so fast - if at all - if it were a higher level?
Keep in mind Germany was the warmonger until I tricked Bismarck into becoming the rogue state. Earlier I made a choice to MPP Japan with China, which pulled Japan into the war with Russia. China was paid off by Germany to form a military alliance against Russia. I then chose to MPP with Germany to get oil I did not have yet, which spawned the whole war against America. The warmongering was a by-product of the MPP defense strategy I chose, at least until I started the war against Germany.

Even that war was started to avoid a surprise attack from Germany.
If you consider what I did before attacking Germany warmongering, then yes, I think I could have been involved in wars at the same pace. I believe the key is to get the AI to fight each other and take your objectives one at a time with all you have. No matter the level, if they are fighting each other I have the chance to make strategic acquisitions to grow the empire. I don't see how the higher levels would have affected that. At deity I may have been steamrolled, or maybe just missed some of the early successes, I just don't know. Perhaps someone with more deity experience could answer that better.