Does the "Find my iPad" service work without WiFi when you aren't paying for cellular service?
No, you can get an app like NetStat and see the ports that open when WiFi is connected as well as when data is available, but not connected.

The carriers would know where it was since their cell towers would have a fix on the IMEI (or equivalent for non GSM carriers) - but that database isn't integrated into the Find My Phone service in any way we can see.

You are correct that the hardware talks with base stations that are near by and it would be nice (kind of like 911 service is permitted even when a line is inactive) for consumers to have this work without respect to billing status.