Is it possible for a membership to be given as a gift? Say, for a non-member to pay and specify the recipient's email address or existing username?

Sorry, it's not quite possible yet. Hopefully it will be before too long.

For now, you would have to sign in as that user and purchase for them from the billing page.

Or, if the recipient didn't yet have a Skritter account, you could create one, credit it, and then give them the login details. The only thing they wouldn't be able to change is the username.