Just to be clear, you have two routing tables, one NAT instance and one Internet Gateway right? The default route (0.0.0.0/0) for the routing table used by the public subnet should be to the Internet Gateway (igw) and the default route in the routing table used by private subnets should be the NAT instance. AWS sometimes set those for you automatically when you use their wizard, but I assume you are setting it up manually since you are setting up the NAT instance manually.
You can set up a bastion host to connect to any instance within your VPC:
http://blogs.aws.amazon.com/security/post/Tx3N8GFK85UN1G6/Securely-connect-to-Linux-instances-running-in-a-private-Amazon-VPC
You can choose to launch a new instance that will function as a bastion host, or use your existing NAT instance as a bastion.
If you create a new instance, as an overview, you will:
1) create a security group for your bastion host that will allow SSH access from your laptop (note this security group for step 4)
2) launch a separate instance (bastion) in a public subnet in your VPC
3) give that bastion host a public IP either at launch or by assigning an Elastic IP
4) update the security groups of each of your instances that don't have a public IP to allow SSH access from the bastion host. This can be done using the bastion host's security group ID (sg-#####).
5) use SSH agent forwarding (ssh -A user@publicIPofBastion) to connect first to the bastion, and then once in the bastion,SSH into any internal instance (ssh user@private-IP-of-Internal-Instance). Agent forwarding takes care of forwarding your private key so it doesn't have to be stored on the bastion instance (never store private keys on any instance!!)
The AWS blog post above should be able to provide some nitty gritty regarding the process. I've also included the below in case you wanted extra details about bastion hosts:
Concept of Bastion Hosts:
http://en.m.wikipedia.org/wiki/Bastion_host
If you need clarification, feel free to comment.
Best Answer
Yes, if the servers in your private subnet really never need to talk to the outside world (they don't download software updates? Don't use public NTP servers?), then you don't need a NAT gateway for them. And the servers in your public subnet don't need a NAT box, they will route through an EC2 Internet gateway.