Does iCloud require any telephone land line infrastructure to send messages?
iCloud depends on the internet for transmission of data. iPhones, unfortunately, aren't capable of being sat-phones at this point (by themselves). As long as both the sender and the recipient have internet access, and as long as both are using iMessage (not SMS), then the iMessage should successfully be sent and received. 

There are obviously multiple ways to get internet through which your phone could be connected. As you are aware, one such way is through cellular towers (if functioning), or another option is through a wifi connection (but again, this must have a landline connection as well). It is possible to get internet through a satellite dish and then broadcast that connection via wifi to your phone.

Again, both the sender and recipient must have internet in order to be able to communicate with iMessage.