How do I create an Ec2 Instance with a Public IP automatically **without** declaring an Elastic IP in cloudformation?

Assuming you are starting your instance in a VPC public subnet (i.e. a subnet that has a routing table incl. a rule to send traffic to 0.0.0.0/0 to the Internet Gateway), just define AssociatePublicIpAddress property in the NetworkInterfaces group of your EC2 resource:

            "NetworkInterfaces" : [{
                 "AssociatePublicIpAddress" : "True",
                 "DeleteOnTermination" : "True",
                 "SubnetId" : { "Ref" : "PublicSubnet" },
                 "DeviceIndex" : "0",
                 "GroupSet" : [ { "Ref" : "SecurityGroup" } ]
            }],

See documentation at http://docs.aws.amazon.com/AWSCloudFormation/latest/UserGuide/aws-properties-ec2-network-iface-embedded.html

If you are starting your instance in EC2 Classic networking (non VPC), it will receive a public IP address automatically.

I see that this is an old post but i post the answer anyway it can be helpful. In the subnet you can set : "MapPublicIpOnLaunch" to True so all the instance of this subnet will have a public IP.

MapPublicIpOnLaunch

Indicates whether instances that are launched in this subnet receive a public IP address. By default, the value is false.

Required: No

Type: Boolean

Update requires: No interruption.