Well, for trisection it's very simple. You could divide angle into $2^n$ parts, then just take $\lfloor\frac{2^n}{3}\rfloor$ parts. Of course it could be made as close to one third as you want, but might be hard to do.
For circling the square - draw the $2^n$-gon, then a rectangle with sides $a_n \cdot 2^n$ and $R/2$ where $a_n$ - is the side of the $2^n$-gon$, and R - is the radius of inscribed circle. then it's easy to transform rectangle into square.
I think it's not harder then constructing the 65537-gon
