Transactions are pretty small, as long as you have some way to relay data to a party that has an internet connection, you can submit a transaction. The party you submit the transaction to does not need to be fully trusted, worst they could do is not submit it to the network.