Can we do zero-downtime kubernetes deployment with a single pod?
Is there anyway to configure K8s to actually bring up a new pod, direct new traffic to it, and only then shutdown the old pod?

This is the default behavior. MaxSurge is number of additional pods that runs during upgrade.
What you also have to check is how the load balancer is handling traffic, does it have capability to detect that you have deployed a new Pod, e.g. is it Kubernetes aware? See Container native load balancing on Google Cloud, it looks like you should have a ReadinessProbe on your Deployment.

Actually I realized what's happening is that the pod is getting traffic routed to it before the app is actually completely ready.

This is the default behavior, if you define a ReadinessProbe for your Deployment. As you write, you can also add a StartupProbe but the ReadinessProbe is most important.