All quadrilaterals, even the nonconvex ones, tessellate the plane. One way to see this is to start from a checkerboard tessellation made by repeatedly flipping squares across their edges, and then note that you can deform the vertices of each square as much as you like and the tessellation is preserved.
As everyone knows, obstructions to geometric constructions always live in some cohomology group or other for completely mysterious reasons. Is there some nice invariant that attaches to a -- I don't know the appropriate object here, maybe some sort of periodic lattice -- that we could have calculated to determine that we could deform the squares of the checkerboard into arbitrary quadrilaterals?
Obviously this could be a pretty open-ended question, but on the other hand I feel like there might be a known answer here, and if so the question is fairly clear-cut. (Feel free to insert additional hypotheses if necessary.)