Can a device pretend to be a USB keyboard?
Yes. This is definitely possible, requiring no modifications or drivers on the PC. As the OP mentions, the USB identification on the phone end is ultimately done in software (in this file https://github.com/android/kernel_msm/blob/android-msm-2.6.35/drivers/usb/gadget/composite.c), and it could be modified to identify itself as a standard USB keyboard. 

This change would require a couple of things.


A modified kernel with a patched USB driver
An Android app that could talk to some interface exposed by the modified USB driver.


There was a paper published a couple of years ago (titled Exploiting smart-phone USB connectivity for fun and profit) that described using a phone to brute-force desktop login screens. The method they used involved making the phone appear as a USB keyboard.