The relay you select to switch the mains will depend on what kind of load it switches: resistive, inductive, incandescent lamps, switching power supply (e.g. computer), etc. The type of load affects the type of contacts used. The relay manufacturer's datasheet should specify the type of load the relay contacts are designed to switch.
For heavy loads, toward the 13 A end of your range, a contactor may be more appropriate. A contactor is a form of relay but usually with special arc-breaking contacts essential for inductive motor loads. Contactor current ratings start at around 10 A and go up from there. You might have difficulty finding a contactor with 5 VDC coil, but you can energize a contactor coil from another relay that does have a 5 VDC coil.
There are mechanically latched relays, really two relays with an interlocking mechanism such that if you alternately pulse the two coils the relays change states: one "pulls in" and the other "drops out". Mostly just a curiosity now with microprocessors controlling everything, and they may be difficult to find and purchase.
A bistable flip-flop can be wired to change states each time it receives a "clock" pulse, but you need to be careful that the pulses are "clean," without any bounce.
A latching relay is typically constructed from a multi-pole relay, for example DPDT, by wiring power for the coil to a normally-open set of contacts and connecting the other contact of the normally-open pair to the coil. When the coil is energized (from a separate path), the normally-open contacts close and apply power to the coil so it remains energized. To make the relay de-energize you must interrupt power to the coil. This can be in the form of a normally-closed switch or a normally-closed contact on another relay that supplies power to both the coil and the latching contacts of the first relay. Briefly energizing this second relay (or actuating the switch) will interrupt current to the coil of the first relay, causing its normally-open contacts to open, and the relay thereafter remains de-energized until its coil is pulsed on again. Clearly all this requires two relays and two sources of pulses. It is possible to design a relay circuit that operates from a single pulsed source, but the circuit is not as simple as either a flip-flop or using two pulse sources.
How much electronics experience do you have? Are you comfortable working with CMOS digital integrated circuits on a prototyping board?