There's a recent paper addressing exactly this question: https://arxiv.org/abs/1802.02263.  (Disclaimer: I'm a friend of the authors and happy to plug their work.... but I promise you'll find it right on topic.)

But to elaborate on the original questions...

• As you've noted, the most important part of the definition is that null trajectories are at 45 degrees and the diagram coordinate patch is finite. You can give a precise definition encapsulating that (above paper does), but don't really need to.

• There's no known general algorithm for all spacetimes. It's true that every 2D spacetime is locally conformally flat, and there's a known formula for coordinates where this is explicit (as postdoc must be referring to). That formula gets you a Penrose diagram for any individual coordinate patch, but in general not for the whole spacetime, since many spacetimes can't easily be covered in a single patch. If you want a diagram of the whole thing, you have to cover it in local patches and match them up properly.

• Diagrams can be either qualitative or quantitative, depending how they are generated. Most of the time they are qualitative, and that's usually good enough. Most of the quantitative variety are special cases (Minkowski, Schwarzschild, R-N, dS, AdS,...), but these are not often plotted quantitatively even when they could be. A systematic method for generating qualitative diagrams for metrics $ds^2 = - f(r) \, dt^2 + f(r)^{-1} \, dr^2+ r^2 \, d\Omega^2 $ is given by Walker's 1970 paper (https://doi.org/10.1063/1.1665393). The paper I cited at the top gives a quantitative version of the same diagrams.

• When they exist, Penrose diagrams are not unique. They can always be stretched by arbitrary functions along null directions. It may be true that they are unique under some suitable equivalence relation, but I'm not sure.

There's a recent paper addressing exactly this question: https://arxiv.org/abs/1802.02263. 

(Disclaimer: I'm a friend of the authors and happy to plug their work.... but I promise you'll find it right on topic.)

There is currently no general procedure, but they give the procedure for a large class of metrics.

To elaborate...

• As you've noted, the most important part of the definition is that null trajectories are at 45 degrees and the diagram coordinate patch is finite. You can give a precise definition encapsulating that (above paper does), but don't really need to.

• There's no known general algorithm for all spacetimes. It's true that every 2D spacetime is locally conformally flat, and there's a known formula for coordinates where this is explicit (as postdoc must be referring to). That formula gets you a Penrose diagram for any individual coordinate patch, but in general not for the whole spacetime, since many spacetimes can't easily be covered in a single patch. If you want a diagram of the whole thing, you have to cover it in local patches and match them up properly.

• Diagrams can be either qualitative or quantitative, depending how they are generated. Most of the time they are qualitative, and that's usually good enough. Most of the quantitative variety are special cases (Minkowski, Schwarzschild, R-N, dS, AdS,...), but these are not often plotted quantitatively even when they could be. A systematic method for generating qualitative diagrams for metrics $ds^2 = - f(r) \, dt^2 + f(r)^{-1} \, dr^2+ r^2 \, d\Omega^2 $ is given by Walker's 1970 paper (https://doi.org/10.1063/1.1665393). The paper I cited at the top gives a quantitative version of the same diagrams.

• When they exist, Penrose diagrams are not unique. They can always be stretched by arbitrary functions along null directions. It may be true that they are unique under some suitable equivalence relation, but I'm not sure.