I'd be tempted to forget the solenoid idea, as they take a lot of power to get long, high force movements and cannot be made small with those capabilities.
How about a couple of off-the-shelf high force metal geared radio control style servos?
Ones with 35Kg/cm torque are not all that expensive, eg.
Description FeeTech 180 Degrees Digital Servo 7.4V 35kg/cm FT5330M Gear type: Steel Limit angle: NO limit Bearing: Ball bearings Horn gear spline: 25T / 5.9 mm Horn Type: Plastic, POM The FeeTech 180 Degrees Digital Servo 7.4V 35kg/cm FT5330M offers a PA+Aluminum case and has an operating...
(And even cheaper on ebay etc).
Could you use two of those as opposing "pushers" to operate the gearchange??
eg. For a gearchange, one or the other would move the appropriate amount to push the changer, pause briefly then move back clear again, so either could always push the changer either way.
Servos such as these can be controlled very simply by any small microcontroller, or even 555 timer ICs with a few added components.
As the exact position is precisely controllable, it would also be a lot easier to select neutral, if that is between two gears?
[My experience is mostly with British bikes & many decades ago.]