Hitler was already losing support by 1933. The problem is, the Nazis had no intention of relinquishing power, and they had suborned enough parties to allow them this. Weimar Germany wasn't really terribly unstable at the fundamental level any more. Most people also desired stability, which was part of the problem. Removing Hitler from government in any kind of violent coup or revolution would have been unpopular even with many non-Nazis.
The next question is who is going to replace him? The Nazi party was not everybody's favourite in 35 and 36, but neither were the Communist or SoPaDE (aside from the fact that a Social Democrat coup is ASB). The military is the only credible candidate I can think of. Maybe if Hitler decides to stand by Roehm and gives the generals the finger... A more moderate military government would be welcomed by many and opposed by few, and the Nazis had already exiled, killed, imprisoned or intimidated most organised opposition, so the takeover could be swift. But how do you make Prussian officers grow a spine?
As to outsiders, I don't see that. The western democracies are utterly discredited with the German public raised on 'Schanddiktat' propaganda, the USSR is a bugbear, and the Fascists support Hitler. Any foreign association (with the possible exception of the Vatican, and that only maybe) will hurt more than help.