My local Credit Union will issue paper cheques on request (not a checkbook: they type up the cheque for you, addressed to whomever you request). But that's an independent Credit Union in Ireland. Still, it may be worth asking.