Printing with Sodium bicarbonate
Are you limited to a mixture of baking soda and water?  If you add a thickener (like agar gum) to the mixture to give it a bit more "stickiness," then you should be able to use rubber stamps (or foam cut-outs, etc...just google "DIY rubber stamps" for alternatives).  Use a foam brush to apply the liquid mixture to the stamp and apply to your paper.  

You will have to experiment with different thickeners (agar gum was just the first one that came to my mind) and amounts to determine what will work best with the baking soda and water mixture.