There are services that work similarly to what you want. You pay them the amount you want + a fee and they arrange to deposit the money into the person/company's bank account but I don't think they send a paper check more than once. RadPad is one for paying rent and I think it will work with other monthly bills.
You'd do better off talking to the trainer about them using a service such as Square and agreeing to pay the ~3% fee they charge for this. The deposit it rather quick so it's about the same as giving a check and the trainer depositing it for clearance.

For the credit card advice we need some more info. Where are you located? (country and city) What's your general credit rating? Principle airline/alliance you travel on? Goal for rewards gained via travel & spending?