Any small engine will have a large magnet on its flywheel to generate voltage in the coil (and then spark for the plug). You should have no problem finding a hall sensor that can detect that; the magnetic flux must be in the tens of thousands because the typical mechanic's test is that it should be able to hold the shaft of a screwdriver parallel to the flywheel without dropping it.
Is this a horizontal shaft Honda clone? You should be able to feel the magnet right through the engine shroud; balance a screwdriver in your fingers and and gently tap it against the right side of the shroud as you slowly pull on the rope.
As most of the inexpensive hall sensors detect in the range of a few 100 gauss you should be able to tape one right to the shroud. Heck, you might even be able to make a small coil with magnet wire and detect the rotation when it induces current in that coil.
See also: http://bildr.org/2011/04/various-hall-effect-sensors/