Use the Pixel Pixel (1x1 square) brush (1x1 squareNOT "1. Pixel" brush!!!) brush:
This brush has its hardness set to 0, and thus doesn't exhibit the 3x3 pixel issue you have encountered. It uses the size set for the paint tool.
In addition to selecting this brush, you should also use the pencil tool if you want pixel-grid-aligned 4x4 stamps and lines. You can achieve the same with other tools by using a actual grid and making sure the tool snaps to it, though.