I don't know about the out of state address part, but it would probably be pretty painful in general to go around stores in the US and try to pay by check these days. Some large stores probably would have the systems to handle it but it wouldn't be normal and would cause a lot of friction. Absent a credit/debit card, you'd be better off just using cash which wouldn't be normal either but would be widely accepted.