1) Если Вы не тривиальны с настройками DNS, можно попробовать что-то как dyndns.com, но это - очень плохое решение.
2) Лучше для подготовки специального сценария автозапуска, который называет nsupdate с надлежащими параметрами. Это действует согласно DNS RFC, таким образом, идеально все серверы должны поддерживать эту функцию. Но так или иначе необходимо узнать, какое программное обеспечение DNS использует сервер.
Вы сталкиваетесь с проблемами производительности со своим текущим приложением?
Если бы определенно необходимо улучшить производительность на уровне HAProxy, то я предложил бы просто использовать отдельный экземпляр HAProxy для каждого субдомена. Например, создайте новый сервер HAProxy и укажите на a.domain.com непосредственно на новый сервер. Можно также продолжить указывать на все записи DNS в основной сервер HAProxy и иметь первый уровень HAProxy, только обрабатывают соответствие субдомена.
Конечно, если у Вас действительно нет проблем производительности, затем возможно, лучше оставить достаточно хорошо одним.