Why do the problems that you state with RDS not true for DynamoDB? Does DynamoDB not run in a VPC?
BTW, you can expose RDS out to the internet.
Interesting, looks like that might be possible after all, though the docs are a bit unclear how this would work from Lambda specifically, and it looks like it needs a NAT regardless. Guess I misunderstood the docs at the time. (This ties into my comment about inexperience being our largest mistake. :))
If you run your Lambda in a VPC, your cold start times get worse, so latency increases.