the mechanical linkage would have to be done on the car and totally custom. And since you're talking about something that moves about 1/4 inch the slack in the linkage would have to be close to zero.
the solinoid would be easier to do but more difficult to make theft proof. Maybe a seperate hidden switch that activates the coil or something like that.

Since the wheel lock relies on a small hard metal pin that drops into a slot on the stearing column to lock it and a basic solinoid (not a door lock solinoid) is an electrical plunger that pulls and pushes a metal shaft that could easily be made into a pin. Mount it on top of the column where the lock hole is and you're done.
I've used a few that have a spring in them to push the pin out while there is no power to it and when it's powered it pulls the pin into it. Should be perfect for this. Search out any good electronics stores in your area(not radio crap), they would have it or could get it for you.