What happens to an embassy when the country it represents stops existing?
It depends on how the country stops existing, but normally there will be some provision for the country's assets to pass to a successor country, whether because the country is being broken up or consolidated with another. If the country's government is simply being overthrown, then the country doesn't actually stop existing, and the new government assumes control of the embassy along with the rest of the country's assets.
What would happen to the embassy staff?
Some may continue to represent their country; others may leave; others may seek asylum to remain.
Under the Vienna Convention on Diplomatic Relations they retain diplomatic status until two things have happened: first, the receiving state (the country where the embassy is) has been notified that their diplomatic function has come to an end, and second, either they have left the country or a reasonable period for them to leave has elapsed. If they remain longer, the specific status depends on the immigration law of the receiving state, although if they seek asylum then their status should be governed by the refugee convention.
Would all the staff become refugees or stateless?
They would not become refugees automatically: they would have to make a claim, and the claim would have to be accepted. Whether they become stateless depends on the nationality law of their country. (Indeed, it is possible for a diplomat, with the permission of the receiving state, to have the nationality of a third country, and any such people are not generally going to become refugees, much less stateless.)
Thanks to Relaxed for reminding me in a comment to add another possibility: if a government in exile arises, the embassy could continue on as a diplomatic mission of that government. This happened, for example, in the second world war, at least with the Netherlands and probably with other occupied countries. Relaxed also mentions some others:
Another scenario after a government overthrow is that some diplomats remain loyal to some minority government or government-in-exile with little or no power on the ground in the sending country. If the receiving country finds it expedient and no new ambassador is named or accepted, and the embassy somehow finds some funding, it can continue to function more-or-less as normal and the situation can last for some time. I think it happened to various representations of Estonia (during the cold war), Somalia (in the late 1990s/early 2000s), and Libya (in the 2010s). – Relaxed 14 hours ago