Short answer: in your current deployments using the Cloud SQL Proxy and managed services in App Engine, you should be able to make this change without incurring downtime.
I recommend reviewing the Cloud SQL documentation on certificate rotation (that document relevant to MySQL; there is a similar document for PostgreSQL). There are a couple of points of note from the documents:
The explicit configuration of SSL/TLS is only required when you connect to the instance directly, using its IP address:
SSL/TLS is needed to provide security when you connect to Cloud SQL using IP addresses.
Where you employ the Cloud SQL Proxy component, this will deal with encapsulating and securing the connection to the database instance on your behalf. This includes the other main benefit of Cloud SQL Proxy: there is no need to explicitly whitelist the IPs of connecting hosts, which may be impossible in a cloud setting where hosts are short-lived with ephemeral IP addresses.
Cloud SQL uses self-signed TLS certificates:
Cloud SQL uses a self-signed, per-instance server certificate
This is important for any applications which connect directly using the IP address. To ensure they are talking to the legitimate Cloud SQL host, such applications should be configured to verify the server certificate on initial connection. As the certificate is self-signed, they can only do so if they have a local copy of the certificate to compare with.
This is the reason for the multi-step update process. You are given the opportunity to download the new certificate and configure your applications to accept both the old and new prior to making it active on your host.
The file downloaded with the new server certificate contains both the current and upcoming (new) certificate, so this is compatible for connections made to the instance irrespective of which version of the certificate is "current" on the server at the point of connection. The most important requirement is that you do not make the "upcoming" certificate "current" until all downstream clients connecting via IP have received the new certificate file, as they will fail to verify the server's authenticity.