The Google Web Search (SOAP) API was deprecated in November of last year, having been discouraged for a long time previously.
I noticed there exists the new Google Custom Search API, but this seems only for creating site-specific custom searches. So, is there currently any API solution for searching the entire web? Either using Google Custom Search or some other API?
Actually, the custom search API will do what you want -
After initially creating your custom search engine, you CAN go back into the control panel / websites link on the left side, and just remove the domain that you were forced to enter when you created the custom search engine.
Once that's done, bingo! you're searching everything, instead of just a site: search