iOS app store falsely claims I have no payment method while gifting app
I called Apple Support and apparently prepaid codes (store credit) can't be used to buy gifts, although this restriction isn't documented anywhere. Posting this answer for everyone to know.

To gift apps without a real debit or credit card: most convenience stores and malls offer special prepaid cards that behave like debit or credit cards. You can buy one of these, plug them into your account as a "debit" or "credit" card, and use that instead.