What is the best way for me to go about writing a new Bitcoin wallet application? Is piggybacking off API's like blockchain.info or coinbase a good tactic? Would the application then be OK to distribute (are said services open source?). Are there alternatives? Can I run my own Bitcoin server and write my own API to go with it instead? What would the steps be involved in that? Would your average punter trust a (legitimate!) wallet that I create or would they feel safer using an app that is built upon a renowned service?
A hosted wallet, which will involve a wallet running on a server that has all the wallets is a bad idea in general. People will not feel safe as they have to trust a third party with their coins and you'd have to implement a whole backend system.
Piggying off Coinbase or a Blockchain is a bad idea, the services themselves may send you a Cease and Desist as you may send a lot of requests and end up swamping their servers, also you'd be copying the functionality of their apps.
You can write a full node, but a mobile phone may not have enough ram and storage to efficiently and quickly do that.
The only nice, viable and realistic approach is creating an SPV client like Electrum for the mobile platform. SPV clients aren't full nodes, they put a certain amount of trust on third parties, but the amount of trust is incredibly small and always double checked. Their main method of work is just requesting data from servers, etc. You can use the Electrum protocol instead of rolling your own as well, you won't need to host servers as well doing that as the community runs Electrum nodes themselves.
You can fork Bitcoin Wallet, an SPV implementation of the Bitcoin protocol:
It's GPL licensed.
Take a look at this:
www.boetchain.com or https://play.google.com/store/apps/details?id=com.boetchain.bitcoinnode
It still very early, so for now, only maintaining connections with peers are available - but it is a start.
Disclaimer: I am a dev on the project