As described in RFC 5280, a certificate has the following overall structure:
Certificate ::= SEQUENCE {
tbsCertificate TBSCertificate,
signatureAlgorithm AlgorithmIdentifier,
signatureValue BIT STRING }
The three elements are the "to-be-signed", an identifier for the signature algorithm, and the signature. If you want to be able to regenerate the exact same certificate, then all three elements must be rebuilt identically.
Most certificate in circulation use RSA "v1.5" signatures, as described in PKCS#1. That signature algorithm is deterministic, so if you use the same private key, same algorithm parameters (the companion hash function), and same input (the to-be-signed), then you will get the same signature. The same does NOT hold for the newer, fancier "PSS" signature scheme described in PKCS#1; that one is randomized and you will get a distinct signature value each time. Similarly, if the key type is DSA or ECDSA, then the corresponding signature scheme is randomized, unless you use a specific deterministic implementation (which is possible but not a given).
Assuming that you use a deterministic signature scheme, then the question reduces to reproducing the same to-be-signed contents. The to-be-signed contains the following:
TBSCertificate ::= SEQUENCE {
version [0] EXPLICIT Version DEFAULT v1,
serialNumber CertificateSerialNumber,
signature AlgorithmIdentifier,
issuer Name,
validity Validity,
subject Name,
subjectPublicKeyInfo SubjectPublicKeyInfo,
issuerUniqueID [1] IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
subjectUniqueID [2] IMPLICIT UniqueIdentifier OPTIONAL,
-- If present, version MUST be v2 or v3
extensions [3] EXPLICIT Extensions OPTIONAL
-- If present, version MUST be v3
}
Most libraries that create "self-signed certificates" will introduce variations in the serialNumber
(since the serial number is supposed to be unique, it will often be randomly generated) and validity
fields. The validity
contains the two dates that delimit the time range of certificate validity; usually, a library that creates a self-signed certificate will use the current date and time for the first date, and, thus, won't use the same value if the certificate is recreated at a later time.
Extensions are, by definition, open-ended, and may contain various random elements as well.
Self-signed certificates, by definition, are NOT certificates; they live outside of the certificate validation process, and that process is the only reason why certificates actually exist. A self-signed certificate is a name and a public key, encoded together into what superficially looks like a certificate out of a mixture of quick and dirty reuse of existing code, long-standing Tradition, and historical confusion. Such a "certificate" is self-signed because there is a non-optional field for a signature, but that signature is meaningless.
Therefore, in a self-signed certificate, most if not all "extensions" will be ignored, and so will be some other fields such as the serial number. You can probably (depending on what your server-to-server protocol requires in these "certificates") fill the fields with dummy, fixed values that will make your protocol happy, and can be refilled identically later on. However, not all existing support libraries will allow that; you may have to rewrite your own certificate encoder (which is doable but at the price of your sanity).