I claim that there is an $N$ so that any rectangle with both sides at least $N$ can be decomposed into squares of sides $4,5,7$ and $9.$ If we show that, then the same applies squares of sides at least $N.$ I will show this for $N=1178.$ With a little more work that number could be decreased to $123$. But that is probably far from  optimal. 


Let $a,b>0$ be relatively prime integers.

It is a result of [Frobenious][1] that any integer $m\geq f(a,b)=ab-a-b+1$ can  be written in the form $m=as+bt$ with $s,t$ non-negative.

Using just $a\times a$ squares we can make a rectangle $a\times ab$ and using just $b \times b$ squares we can make a rectangle $b \times ab.$ Using those blocks we can make a rectangle $m \times ab$ for any $m\geq ab-a-b+1$

Hence 

- Using $4 \times 4$ and $5 \times 5$ squares we can make a rectangle $20 \times m$ for $m \geq f(4,5)=12.$

-Using $7 \times 7$ and $9 \times 9$ squares we can make a rectangle $63 \times m$ for $m \geq f(7,9)=48$

- Using all four sizes of squares we can make any rectangle $m \times n$ provided that $m \geq 48$ and $n \geq f(20,63)=1178.$




  [1]: https://en.wikipedia.org/wiki/Coin_problem