As others have said, throwing is the best exercise for throwing. Long toss, long toss, long toss. The core exercises (esp. ‘chopping’) mentioned upthread would be a good place to begin adding power.
I think you’re too focused on shoulder strength; It’s important, but the bulk of the stress placed on the shoulder in a proper throwing motion comes after the ball is released. Strengthen it certainly, but don’t expect to gain much power there.
As to exercises for it, I would focus on proper stretching before and after throwing, and probably the single best exercise (to ward off injury, rather than add power) would be lying on your side (throwing arm down), keep your elbow at your side, bent to 90 degrees from your torso. Palm upward, grasp a light dumbell (5-10lb) and raise it to your opposite hip to exhaustion. Sort of an arm wrestling motion with your elbow fixed to your hip. Flip over (throwing arm up) and repeat with the same arm in the opposite direction (raising the dumbell). You’ll feel it in the top of your shoulder in short order.
A tip-Many weekenders I see throw with a dead lead arm, which is to say, their off hand just sort of flops out front and their core isn’t properly coordinated. They throw all arm.
The throwing motion is too complicated to express here, but the position you are looking for (for a standard overhand to 3/4 delivery) is this-When the lead foot hits the ground, your elbows (both of them) should both be at shoulder height and on the same plane, as if you had a rod running elbow-shoulder-shoulder-elbow. From there, you drive the lead elbow down past your lead hip as you snap your hips open and your throwing arm comes through.
A good drill for this is to constantly keep a another ball (perhaps a tennis ball or baseball) in your *glove * hand while playing catch. Keep the ball in the palm of your glove, not the webbing, so that you must constantly think of that hand, and consequently what that arm is doing. Feel free to pause when your lead foot comes down to check your elbow positions from time to time.
You’ll look like a goon warming up, but you should pick up a couple MPH and some accuracy in a matter of weeks/months.