Composite video is very forgiving and you can definitely use relays to basically perform the same function as unplugging camera 1, and plugging in camera 2, and vice versa.
In your diagram, however, you show using two relays and a "Y" splitter, which could lead to the possibility of both video signals being active at the same time, resulting in a scrambled video signal.
Instead, consider using both throws of the same relay so that your inputs from each camera are connected to the throws, and the output is connected to the pole. In this manner, only one camera will ever be connected to the output to the PC at one time. The down side is that you will have to keep the relay energized continually for one signal (power consumption), and off for the other. (A latching relay could avoid this problem.)
Looking at your Arduino relay board, the relays appear to be SPDT (single pole double throw), so you'd need to connect the shields (ground) together. The following diagram shows this:
I removed the diagram showing a DPDT relay because I goofed up; both Camera 1's composite video pins were going to the same throw on the relay. Doh! I revised the text to be applicable to the relays you have.