I have edited my sudoers file as follows:
ubuntu ALL=(ALL:ALL) ALL
There's no need to edit sudoers on Ubuntu EC2 instances. It's already set up for passwordless sudo in /etc/sudoers.d/90-cloudimg-ubuntu
Should I terminate my instance and start again?
Yes, based on what you've said, I would recommend start with a fresh instance. By editing the sudoers file to require a password for an account that does not have a password, you have effectively locked yourself out. (I've written an article that describes how to recover from a broken sudoers, but in your situation starting fresh is much easier.)
what public key should I be including in ~/.ssh/authorized_keys?
You can simply leave authorized_keys
alone and ssh in the same way that you did in the first place, using the ssh key you specified when you ran the instance. Or, you can add any other ssh keys you want to give access just like you normally would when managing an Linux box. Once the instance is started, there's nothing EC2-specific about ssh key management.
In general, I recommend uploading your personal public ssh key to EC2 and then specifying that name when starting new instances. This makes it easier to ssh in to new instances using your default ssh key. Here's an article I wrote about that: http://alestic.com/2010/10/ec2-ssh-keys