So stall current is probably 5 to 10A range.
Any supply that can provide around 5A continuous and tolerates temporary overload without
cutting out would do. For instance a 6V lead-acid battery would be quite good.
For mains supplies you have to worry about cut-out behaviour - lots of supplies react to overload
by cutting out completely - which doesn't play nicely with stall current spikes. You can just go for the
over-engineered approach (supply can handle stall current easily), or be careful in ramping up PWM
levels to each motor to avoid large stall currents flowing.
Yes, definitely a separate supply for the motors (for several reasons), common the grounds. A USB
charger is a good way to power the Arduino, and note that the two supplies are going to have grounds
commoned, usually this isn't a problem, either they will be isolated or mains earth will already be connected
to the 0V output.