The solenoid is an interesting idea. Unfortunately, most of the solenoids I could find required high voltage (12/24V) and didn't move fast enough to get significant motion from a wall push.
How do you know how fast they move?
The magnitude of a push is a combination of speed AND strength.
Do they make any solenoids that move quick enough to make something fly and use only 4.8/6 volts?
Usually, they're a few ms, but if you want to push a few thousand grams, they'll be much slower and the longer the stroke, the weaker they are.
The types made for low voltage just have fewer turns of a thicker wire and will use a much higher current.
The half-toothed gear is an interesting idea. Do you know of any companies that sell half-toothed gear for use with standard servos
Find a suitable regular gear wheel than can be mounted to a (strong) servo horn and grind of half the teeth.
Why do you want to push out from a wall like this - don't you use a motor for normal motion?