Will this relay handle the current and voltage requirements

You can place the RC either at the B side or the A side. When components are placed in series the order of them doesn't matter for the working.

About the diodes. When you switch off the relay it will cause a (possibly large) negative voltage on the FET's drain, and a flyback diode is used to limit that voltage to a 0.7 V diode drop. So the diode(s) don't serve to protect the coil, but the FET. Using the zeners will allow this voltage to go to -5.7 V or -15.7 V if you'd use the 15 V zeners. There's no reason for taking risks here, even if the FET can handle -30 V. So I would just use a rectifier or signal diode, or even better a Schottky diode.

edit re your comment
You can indeed use a zener (combined with a common diode, D1 doesn't have to be a zener) to decrease switch-off time, and Tyco also mentions it in this application note, but I don't read it as if they insist on it. The scope images in the first link show a dramatic decrease in switch-off time, but that measures the time between deactivating the relay and the first opening of the contact, not the time between first opening and the return to the rest position, which will change much less.

edit re the 6 V relay and the RC circuit
Like I says in this answer you can operate a relay below its rated voltage, and since its operate voltage is 4.2 V the 6 V version of your relay can also be used at 5 V. If you use a series resistor not higher than 9 Ω you'll have that 4.2 V, and then you don't need the capacitor (keep an eye on the tolerance for the 5 V!). If you want to go lower you're on your own; the datasheet doesn't give a must hold voltage. But let's say this would be 3 V. Then you can use a series resistor of 32 Ω and you'll need the capacitor to get the relay activated.

Operate time is maximum 15 ms (which is long), so as the capacitor charges the relay voltage shouldn't go below 4.2 V until 15 ms after switching on.

Now we have to calculate the RC time for that. R is the parallel of the relay's coil resistance and the series resistance (that's Thévenin's fault), so that's 19.3 Ω. Then

\$ 3 V + 2 V \cdot e^{\dfrac{- 0.015 ms}{19.3 \Omega \text{ C}}} = 4.2 V \$

Solving for \$\text{C}\$ gives us 1500 µF minimum.

Re switching off:
You can't violate Q = CV, it's the Law. Your clamping voltage is 3.3 V + 0.7 V = 4 V. That means that when you switch the FET off the low side of the capacitor momentarily will be pulled to -4 V, and quickly rise again to 0 V. The high side is 2 V higher, and will simply follow that 4 V drop while the capacitor discharges through the parallel resistor. The capacitor won't even notice the drop. The discharge time constant is 1500 µF \$\times\$ 32 Ω = 48 ms, then the capacitor will discharge to 20 mV (1% of its initial value) in 220 ms.

The 62 mA won't charge nor discharge the capacitor. We often apply Kirchhoff's Current Law (KCL) to nodes, but it also applies to regions:

Draw a boundary around C1 and R1, and you'll see there's only one path to the outer world since the way to the FET is cut off. Since the total current has to be zero there can't be any current through that unique connection. The coil has to take care of the 62 mA on its own, and it does so by using the loop formed by the zeners.

Some things to think about as you proceed.

• SSR drops \$1.6V\$, according to your link. At \$12A\$, you are \$\approx 20W\$ dissipation with the SSR. I'd plan for even more dissipation to be safer. You need to consider an attached heat sink for it.
• EMR relays can come powered either by the AC line voltage (using a shading pole or shorted turn embedded into one end of the armature) or some DC voltage. You could consider using an AC relay that operates from 240VAC and including a MOC3023 or MOC3063 (one triggers at the zero crossing, the other doesn't care) opto in order to turn it on safely. This moves the relay power requirement to your line instead of your DC supply for the AVR, though you still need 5mA for the opto. But the coil dissipation for the EMR you listed is 0.9W. And any power supply you use for your micro system will have to include that. That's a lot, by comparison. So "shifting the load" may offer an advantage worth considering.
• If you want to get fancy (and since you are including a micro, you can do that), you could consider the combined use of an SSR and EMR. The SSR is triggered first and operates for some designated period of time while you then activate the EMR and wait for it to be engaged. Then drop out the SSR, leaving the EMR handling the load. A similar process turns things off, as well. You may be able to consider avoiding the heat sink on the SSR this way, if you can assure yourself that you won't overheat it. (Or you can get fancy and possibly even include a bimetal switch taken from a fish tank heater, for example, that will open if things get hot -- which may be smaller than the heat sink.) But another advantage is that the contacts on the EMR won't be subjected to arcing and so will probably last longer, as well. This is called a "hybrid" relay. You can google it. You will have to carefully consider your situation if you do this, though. It has advantages and disadvantages.
• A relay I chose looked like this: JQX-40F 1Z 40A 110VAC. But I'm working with 110VAC here. But that provides another kind of mounting you might look for.

Just some thoughts to consider. Since you will be putting this into a proto box of some kind, mounting is probably best left to your ingenuity.

RESPONSE NOTES:

• The EMR you linked specs \$\approx 1W\$ to hold it engaged. Actually, within spec, it could even be slightly more. At \$5V\$, that's \$200mA\$. Your DC power supply will need to support that load, plus whatever else is required of your DC supply. By comparison, a MOC3023 requires \$5mA\$ to operate an AC relay coil, which itself draws its power from the line and itself only uses perhaps \$30mW\$. It's lower power all around. I'm not telling you to use one. Use what you feel is best. I'm just suggesting an alternative to consider.

• Don't use the SSR to power the EMR. I was offering a thought about using an SSR in parallel to an EMR. For more details, I suggest you google "hybrid relay" and see what comes up. In this case, you protect the mechanical contacts of the EMR using an SSR. There are some nice youtube videos illustrating the elimination of arcing under power using this method. But since what I wrote wasn't clear, I recommend you avoid this idea for now.

ADDITIONAL RESPONSE NOTE:

^{simulate this circuit – Schematic created using CircuitLab}