well, if u wanna house your own DNS, then am afraid down time is an option you may have to consider..... when u decide to change the authoritative name servers for your domain from Network Solutions, u will have a down time of at least 24 hours, as the new records are propagated over the net.....
one way to avoid downtime would be for u to configure DNS servers at your place with your DNS info, and run them as the primary and secondary for your domain... and then ask your ISP to transfer a copy of the records to their DNS server and play secondary DNS server to your domain.... the Network Solutions database has your ISP as the primary authority for your domain, so to begin the migration, u may ask Network Solutions to setup your secondary DNS server as the secondary authoritative DNS server for the domain, after your ISPs DNS server..... once this has propagated, u should then again ask Network Solutions to setup their database so that your primary DNS server becomes the primary authority for your domain... taking the ISP out of the picture.. but maintaining uptime for your domain, as when the ISP has been dumped, your domain records will be handled and resolved by the secondary DNS server u setup at your place, until the records for your primary DNS server have been propagated, after which your primary should handle all requests.....
remember though, that u will need a public IP address for the primary and secondary DNS servers at your place so that they can be easily reached over the internet to answer queries during the migration...
good luck..