At the moment, I have the following set up:
A records:
mydomain.com - aaa.aaa.aaa.aaa
subdomain.mydomain.com - aaa.aaa.aaa.aaa
NS records:
mydomain.com - ns.mydomain.com
What I want to do is to keep the subdomain at that IP address and move mydomain.com to a new server (bbb.bbb.bbb.bbb and ns.newserver.com). Is this possible, and what records do I have to add?
You don't need a separate nameserver.
You are free to make as many A records as you like, pointing to as many IP addresses as you like, all on one nameserver.