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.
Let's design for worst case, that is a good practice.
\$Ic = 133\text{mA}\$
\$h_{FE} = 30\$ # according to the datasheet minimum 30, typically much better; @Ic=100mA
You can calculate Ib now:
\$I_b = \dfrac{I_c}{h_{FE}} = \dfrac{133\text{mA}}{30} = 4.43\text{mA}\$
\$V_{BE,SAT} = 0.95\$ # datasheet, nearest match is 50mA. Maximum value, practical value is probably much lower (0.65V)
Now let's calculate the base series resistance. This is equal to the voltage across the resistor, divided by the current through it. The current through the resistor is the same as the base current. The voltage across it is the rail voltage (5V) decreased by the base-to-emitter voltage of the transistor V(CE,sat).
\$R_B = \dfrac{U_{R_b}}{I_b} = \dfrac{V_{CC} - V_{BE}}{I_B} = \dfrac{5 - 0.95}{4.43/1000} = 913\Omega\$
With all the worst case engineering up to here, for once let's just round it up to the nearest E12 resistor value of 1kΩ (or 820Ω for worst case engineering, it will work with either).
Best Answer
Tony's already provided an approach for you to follow. I'd like to suggest another. I'll return to a short discussion about your question, though, later. You write:
I would have wanted to also consider the use of a mains-powered relay and the use of a MOC30x3 device (MOC3063 if you want zero-crossing behavior or a MOC3023, if not.) These guarantee operation when provided with at least \$5\:\textrm{mA}\$.
simulate this circuit – Schematic created using CircuitLab
This provides opto-isolation, requires a driving current that is routinely available in typical I/O pins from a microcontroller, and powers the relay directly from the mains supply instead of your DC supply rail. And since the relay is AC mains powered and isolated from your DC rail, a simple connection without snubbers works well enough. Just to add still one more useful point, it can be driven directly from your \$3.3\:\textrm{V}\$ I/O pin and there's no particular need for a separate \$5\:\textrm{V}\$ rail.
An OMRON G2R provides some mains powered options and might be such a relay choice.
However, if you must use a separate \$5\:\textrm{V}\$ rail and a compatible relay, then you should operate the switching BJT in saturated mode (active, saturated.)
An early thing to consider is the size of the BJT. In this case, you need a collector current of \$I_C=\frac{5\:\textrm{V}}{100\:\Omega}=50\:\textrm{mA}\$. A saturated BJT will have a \$V_{CE}\approx 200\:\textrm{mV}\$. So that means \$200\:\textrm{mV}\cdot 50\:\textrm{mA}\approx 10\:\textrm{mW}\$. But there's more. The base current isn't accounted for, yet. This will be roughly 10% of the collector current (over-driving the BJT is how you get it into saturation), or about \$5\:\textrm{mA}\$. This will probably require about \$V_{BE}\approx 700\:\textrm{mV}\$. So, another \$700\:\textrm{mV}\cdot 5\:\textrm{mA}\approx 4\:\textrm{mW}\$, for a total of \$14\:\textrm{mW}\$. This is easily within the capability of almost any package, so a small signal BJT like the one you picked out will work just fine.
Note here, by now, that you don't need a base current more than about \$5\:\textrm{mA}\$. So, your base resistor needs to be only about \$\frac{3.3\:\textrm{V}-0.7\:\textrm{V}}{5\:\textrm{mA}}= 520\:\Omega\$. Because this is based on an over-driven 10% figure and because you can rely on the fact that small signal BJTs will saturate well before reaching that figure, it's just fine to relax the base resistor to the next standard value above that figure, or \$560\:\Omega\$. (Probably would work fine with a \$1\:\textrm{k}\Omega\$, but whose counting?)
Tony's suggested circuit with the diode is just fine, by the way, and you should include something like that included diode in order to allow the relay coil a method to de-energize itself when turned off. The time required to de-energize will depend upon the voltage developed across the relay coil, however. And a simple diode presents only a small voltage across the coil, so the time will be longer than it might otherwise be. If time matters to you for reasons you didn't mention, you could consider the idea of including a series zener, as well, in order to jack up the de-energizing voltage and thereby reduce the required time for that phase of operation.
Note that both the AC-powered relay and also the DC-powered option require about \$5\:\textrm{mA}\$ from your I/O pin. The AC-powered method is just an alternative approach to consider and it may expand your options (if not this time then perhaps another time and another place.)