AWS Elasticache/Redis Access Outside of VPC?

I think in your cases there are 3 possible solutions:

1. Like one of the folks said above, deploy our own NAT instance on EC2 instead of using AWS NAT Gateway which can be quite expensive. But of coz you will need to setup / maintain and scale the NAT instance yourself.
2. Deploy a proxy in EC2 in public subnet of the VPC, said deploy a Nginx and set proxy_pass to the ElastiCache cluster in the VPC. In this way your lambda outside VPC can call the Nginx Elastic IP for ElastiCache requests. But please consider to put Network LB in front of an auto scaling group of Nginx EC2 for resiliency. Main concern in this solution is security, your nginx security group need to open 0.0.0.0/0 for EC access (as lambda outside VPC come with different public IPs and no security group itself), ensure you enable encryption in transit and access control using AUTH or RBAC in Redis (if your EC is redis for example)
3. Both 1 and 2 involve building a EC2 instance yourself which increase maintenance burden. I think the best solution is to breakdown your Lambda function into two functions, one handle the EC call (Lambda A) and the other handle the internet API call (Lambda B), put Lambda A in VPC while keep Lambda B outside VPC, and simply use invoke API to call Lambda B from A or vice versa. This should be the best solution but involves more work in coding perspective.