Since many provider switched to TLS only connections, I cannot deliver to gmail anymore with a default plaintext postfix setup.
My question is, can I use valid TLS / does google accept TLS with a self-signed cert?
If not, my only option would be to use a mailserver with a valid cert; e.g. I could use a gmail account to deliver mails, right?
It is the server that is receiving the email that needs a certificate. You don't need one unless you are receiving email on your server AND want to force people to use TLS. Most systems do not verify the cert, and use it only for encryption, so a self signed one will work.
Even then, usually TLS is only required on an alternative port, not port 25. The alternate port is used for clients to send mail through your server. Server to server connections are almost always done on port 25. Since not all mail servers support TLS, mail is almost always allowed unencrypted.