In Ephemeral Diffie-Hellman, the key pair is generated every time.
In practice, does this mean I never need a certificate? Or that means I need a new cert every single time?
You do need a certificate, because the Diffie-Hellman parameters have to be signed. Diffie-Hellman only makes sense if the client can rely on the authenticity of the parameters (meaning: they actually come from the server). Otherwise a man-in-the-middle attack would be trivial.
You just need a standard RSA (or DSA) certificate. In fact, the only difference between DHE-based cipher suites and “classical” RSA suites is how the certificate is used: With DHE, the certificate is only used for signatures, not for encryption.
DH only takes care of the key-exchange. In practice you will need some form of authentication, eg. RSA or DSA for TLS. IPSec also allows pre-shared keys. Without authentication the communication will always be susceptible to man-in-the-middle attacks.