You'll need to find a domain registrar with a hosted DNS service (as you haven't mentioned you will be running one yourself).
Unfortunately my company doesn't offer this, but I'd recommend
Namecheap. Despite the name, they are actually an excellent customer-service orientated company.