my lambda function can send message to SNS with publish method with "no VPC", but it will timeout when I put it in a VPC which has access to public internet with route and internet gateway.
I have my lambda in a public subnet which has 0.0.0.0/0 already routed to the internet gateway, so can not route it again to NAT. Is that possible to assign a EIP to lambda function
You have to add a NAT Gateway to your VPC in order for Lambda functions (and other things in your VPC that don't have a public IP) to access anything outside the VPC. You should read the Things to Know section of this AWS announcement.
Outside Internet is not accessible when VPC is enabled. So, when you send a request to publish to a SNS topic using libraries such as boto3, your requests will timeout.
NAT is one of the option but a more cost effective way would be to setup an interface endpoint to SNS from your VPN. You can go to AWS VPN console and create an endpoint and select SNS as the service.
Here is more details on how to setup your interface endpoint: https://docs.aws.amazon.com/vpc/latest/userguide/vpce-interface.html#create-interface-endpoint
