The best way to implement this is to just request a signature over SMS, and charg a miniscule fee for processing the transaction.
i.e. have software on the phone generate the digital signature (I'm assuming most of these phones can still run some form of custom softwar, even if they have no Internet)
1. RECEIVE INVOICE TRANSACTION IN SMS TXT (INCLUDES TINY FEE FOR PROCESSOR)
2. COPY + PASTE INTO SOFTWARE
3. GENERATE SIGNATURE
4. COPY + PASTE BACK INTO SMS
5. PROCESSOR SUBMITS TO BITCOIN NETWORK