You are asking two very different, but related, questions:
How is separation provided in procedural airspace? (that is, airspace where no surveillance exists)
What are the emergency procedures when a surveillance system fails?
I will address them in that order.
There are three main types of separation: vertical separation, horizontal separation and separation in the vicinity of the aerodrome. I am going to assume you are not asking about separation in the vicinity of an aerodrome. We can divide horizontal separation further into three parts: lateral separation, longitudinal separation and radar separation. Obviously, radar separation does not apply in procedural airspace.
Common for all separation types, when used in procedural airspace, is that they are based on position reports made by the pilots. When we do not have transponders to broadcast the position and level of flights, the pilots have to manually tell us where they are.
Vertical separation is pretty straight forward. It is very easy to apply, and we often prefer vertical separation (even in radar airspace), simply because it is so easy. Vertical separation is obtained by requiring aircraft to operate at different levels expressed in terms of flight levels or altitudes. In most areas today, 1000 feet is the minimum vertical separation. 2000 feet is still used as minimum in some places. For more details, you should research Reduced Vertical Separation Minima (RVSM).
Lateral Separation is obtained by requiring aircraft to fly on different routes or in different geographical locations, as determined by visual observations, use of navaids or RNAV equipment. The idea is, if two aircraft are flying in two different places, then they won't collide.
One example of application of lateral separation is two aircraft flying on two different radials of the same VOR (radio beacon). If the aircraft are established on radials diverging by at least 15 degrees and at least one aircraft is 15 NM or more from the VOR, they are separated - per definition, regardless of the actual distance between them.
Another common example is approach procedures and different holding patterns. Certain procedures are designed in a way that ensures sufficient separation. For example, an NDB approach procedure might be separated from a nearby holding pattern. Again, we do not care about the actual distance between the aircraft - the two procedures are separated, by definition, if that is how they are designed.
Longitudinal Separation is used for aircraft at the same level, flying on the same, reciprocal or crossing tracks. Longitudinal separation is based on time or distance. For example, two aircraft following the same route are separated if there is 15 minutes between them. That is, if aircraft A reports overhead point XYZ at 09:12 and aircraft B reports overhead point XYZ at 09:30, they are separated.
Now, 15 minutes is a long time, and it can be reduced in certain circumstances, but these are the kind of rules we have to follow in procedural airspace (when vertical separation cannot be used). There might be a hundred miles between two aircraft with 14 minutes between, but they are not separated.
You can also base longitudinal separation on distance, if two aircraft are operating directly to or from the same DME (distance measuring equipment). In this case, the minimum separation is 20 NM (and can be reduced in some cases).
In addition to the two above rules (15 minutes or 20 NM), there are many, many rules regarding crossing tracks, reciprocal tracks, separation during level changes, separation between aircraft with different speeds, and so on. Common for all of them is that the pilots will have to report their position, and then the controller has to apply separation in accordance with the rules.
That sums up the separation methods and minima in procedural airspace. Now for your second question: what if radar airspace suddenly becomes procedural airspace as a result of a system failure?
Needless to say, this is extremely rare. Systems are very reliable, and there are backups, and backups of backups. That aside:
The first thing to realise is that this would most likely be considered an emergency situation, which means that normal rules and regulations do not apply. Many pilots don't realise this, but the word "mayday" is not actually reserved for pilot use only. You will likely hear a transmission from the ATC unit that sounds something like "Mayday, mayday, mayday, all stations, radar service terminated due to equipment failure, stop transmitting, standby for further instructions". At this point, you should make sure the volume of your TCAS is turned up...
However, it is important to remember that controllers are trained to handle situations like this. Local procedures are different, but the controllers will either attempt to establish procedural separation, or transfer traffic to adjacent units, if they have radar available. Even when the system fails, the controller will have some way (besides memory) to keep tracks of all the flights in their airspace. This could be physical flight strips, or an electronic equivalent.
The first thing we will do is probably try to establish lateral and/or vertical separation. The idea being, if all aircraft are flying in different locations, or at different levels, they will not collide. We are allowed to use half the normal minimum vertical separation (that is, 500 feet) in emergencies, and this essentially doubles the number of vertically separated levels available. Do not be surprised if you are instructed to fly at flight level 375.
What happens next depends entirely on the details of the outage. Traffic toward the affected areas will be kept on ground or rerouted, and adjacent ATC units with radar coverage will assist in evacuation of the airspace, which will most likely remain empty until the situation is solved. Controllers operating in radar airspace are probably not certified to provide procedural separation, so once the airspace is evacuated, it will remain empty until the system is back up - it cannot simply be changed to procedural airspace and normal operations resumed.