Resistance between any 2 nodes on an infinite square grid

Yes, it is possible. For example Kevin Brown did here and here including this table.

so for the xkcd problem the answer is $-\frac{1}{2}+\frac{4}{\pi} \approx 0.773$.

As far as I know, the first solution to the general problem is given by Cserti,

József Cserti. Application of the lattice Green’s function for calculating the resistance of an infinite network of resistors. Am. J. Phys. 68 no. 10, pp. 896 (2000). doi:10.1119/1.1285881, arXiv:cond-mat/9909120 [cond-mat.mes-hall])

using lattice Green's functions (and there are references to previous partial solutions). For your first question, the recurrence relation that gives the resistance between nodes in a square lattice is equation 32. The paper also describes how to solve or derive asymptotics for rectangular lattices, triangular lattices, honeycombs, and cubic lattices in higher dimensions.