You don't have to knit the entire square. You can knit over half the cast on sts (that'll be about 4.5 x 4.5") as long as you take into account the pattern repeat for some of the squares. You should always work a greater than 4" gauge swatch anyway so that you can measure over the center 4".
You only have to do this once for each pattern (5 different patterns), not each time you knit a square. It does take time but this way, you'll be able to end up with squares that are about the same size (9x9") and easy to match up and seam.
Some of these patterns, like the cables are very stretchy so you'll have to measure gauge over a moderately stretched swatch. Yes, start with the recommended needle size and adjust from there. If I need to change needle size, I just knit onto the new needle and keep going on the same swatch. Just mark where you changed needles.