I've got a setup where I have my app servers (two of them) are running on different instances than my Solr server (just one of those), which is essentially the same thing you're trying to do. So it's definitely possible to set up. Solr is just a service that runs inside of a Tomcat server and listens for queries on a port. So assuming that the port you need is open both in your EC2 security group and on your shared hosting server so the two can talk to each other, I don't see any reason why you couldn't host Solr on an EC2 server and use it with your shared hosting server.
The only other thing you'll probably need is a Magento extension to hook into Solr. We use Solr Bridge on our site and it works really nicely.
It's a bit pricey, but I think there's some free ones out there that would work too. You'll just need to shop around on Magento Connect or roll your own. I don't really want to link any because Solr Bridge is the only one I've worked with so far.