Since you seem to have a budget constraint, I would suggest going with the free tier of Amazon's EC2 service (Google App Engine won't work as it only lets you implement an xmpp client, not a server). You can host any XMPP Server on your Amazon EC2 instance. Ejabberd seems to be a popular choice.
I think you're in the right general direction, once you have your XMPP Server installed and running, you can easily connect whatever client you want to it.