For starters, you'd be able to select "Can be gifted" in the Admin CP under "Edit User Upgrade":
Full size image.
Once you've selected a specific account upgrade to be giftable, a "Gift" button would show up next to "Purchase":
Once you've clicked the "Gift" button, you'd get a pop up that would ask for the username, and have an optional field to PM the user you're purchasing an upgrade for letting them know that you gifted them the user upgrade.
It'd look sort of like this:
Once you click "Gift User", it work exactly like the current system does - it'd take you to PayPal, and then return you.