How are aircraft separated in a non-radar environment?
For oceanic airspace, flights proceed along specified tracks and altitudes specified in their filed flight plan. From there, once they leave radar-controlled airspace, radio reports are made to ATC, who ensure that aircraft are appropriately separated if a flight needs to change its track or altitude. See the wiki article the North Atlantic tracks, which give a good overview on the track system. Specifically:


  Prior to departure, airline flight dispatchers/flight operations officers will determine the best track based on destination, aircraft weight, aircraft type, prevailing winds and Air Traffic Control route charges. The aircraft will then contact the Oceanic Center controller before entering oceanic airspace and request the track giving the estimated time of arrival at the entry point. The Oceanic Controllers then calculate the required separation distances between aircraft and issue clearances to the pilots. It may be that the track is not available at that altitude or time so an alternate track or altitude will be assigned. Planes cannot change assigned course or altitude without permission.


and


  Contingency plans exist within the North Atlantic Track system to account for any operational issues that occur. For example, if an aircraft can no longer maintain the speed or altitude it was assigned, the aircraft can move off the track route and fly parallel to its track, but well away from other aircraft. Also, pilots on North Atlantic Tracks are required to inform air traffic control of any deviations in altitude or speed necessitated by avoiding weather, such as thunderstorms or turbulence.


I'm going to leave the "what happens when things break" to someone else.