Podrías usar las DNS de GoDaddy o sea configurar el dominio para que use las DNS en las que tu puedes configurar los registros A y allí poner la IP del VPS.
Se llama Total DNS Control.
Aquí explican como configurarlo:
http://help.godaddy.com/article/681
Ahora si quieres tener DNS propias del tipo:
ns1.tudominio.com
ns2.tudominio.com
Deberías correr un servidor BIND en tu VPS si usas cPanel ya debería estar instalado por defecto y allí desde WHM configurar las DNS esto se hace en Edit DNS Zone y luego sólo quedaría de GoDaddy registrar las DNS.