Yes, a standard coil relay would work fine, although you might get sick of the constant clicking!
PWM just sets the amount of on-off within each cycle. If your cycle was 1s, then when cold, your heaters would be on for 1000ms each cycle (100% PWM duty cycle). That would gradually drop to 0ms (0%) as you get closer to - or exceed - your required temperature set point. (So for 200C you could just subtract 5ms per degree of temperature increase: i.e., "on time" = 1000 - (temp * 5).)
You just need a 1s loop (or thereabouts): Measure the temp and calculate the on time, then set a pin high, wait for the required ms, then switch it back off. Wait for the remaining time to elapse and repeat. (It's essentially the same as analogWrite(), except you have complete control over the timings by manually "bit-banging" the pin on and off. As you say, as fast as you want up to the limit of the MCU clock frequency.)
Because you have two set points, you'd need to pass to a second loop after the first (with a different "on time" formula), and to get the required rise times you'd either have to write some more sophisticated code, or just fine tune your formula by some experimentation. If your temps and times aren't super critical, then a simple approach like this should get you in the ball park.