I struggled with the same question on a recent project of mine where I wanted to talk to Trello and Salesforce in pure VBA without installing any plugins, opening up Visual Studio, or other hacks. Ended up writing my own library (based heavily on one of my favorites, RestSharp).
It's working awesomely in Excel 2010 and 2013 (and most likely 2007) and I've got it working with Salesforce, Trello, Basecamp, Google Maps, and it should work with pretty much any webservice.
Some fun features include Mac support(!), authentication (Http Basic, OAuth1, OAuth2, and others), Async support, and JSON parsing (thanks to VBA-JSON)
Wow. Great piece of work, have not tested it yet, but looks awesome. Thanks a lot!