Reading around I can see that Android Market doesn't yet support Gift tokens or similar, and while Amazon's Android market does, its only available in the USA. So the question is, what sort of workarounds are there for this?
For example, could I log in to android market from the recipients phone with my google credentials, buy and then download the application, then logout again? Would the application still work? Can I pay with my credit card with the other persons Google wallet? Is this consistent with the usage policy of the Android market? What other options might I have?