Yeah, if you don't need accuracy or calibration, just on or off, then it should be a fairly simple thing to do. You can go with a straight current transformer for a known output (and still pretty cheap), but you can literally take some regular wire, wrap it around your mains line for a few turns, send that through an opamp with a good bit of gain, then send it throw a peak and hold circuit (more op amps) or rectify it and put it into a cap or something and just sample from there. As a proof of concept, I took a 6" breadboard lead, wrapped it three turns around my tablet's charging cable (AC side of the brick) and hooked it up to my scope... about 10mV peak to peak over a noise floor around 5mV - more than enough to get usable on/off data and this is with a loose winding outside of the insulation of the main cable.
The relay seems like a pretty solid plan too, so you have options.