You would only need to change the settings on one server.
Whichever server the DNS is pointing to for mydomain.com, you will setup an alias to redirect a URL to the other server.
So if the DNS is pointing to the server that does not have the cgi bin, the you create an alias to point mydomain.com/cgi-bin/ to 12.34.56.78/cgi-bin where 12.34.56.78 is the IP number of the machine that will hold the cgi-bin
If the DNS is pointing to where the cgi-bin is, then you just create an alias to point mydomain.com to 78.56.34.12 wheere 78.56.34.12 is the IP number of the machine without the cgi-bin.
Im not aware of any other ways to do what you want to do with Apache. If one of the servers is running a different web server then that might be a different story.
Regarads,
Gerald