Many apps are open source (e.g., github, wordpress, coinbase, 2FA apps compatible with many services) and so are available through f-droid. Others, like TextSecure are really easy to build from source and install.
I have occasionally downloaded apps through one of the APK downloader services mentioned in the article comments -- I've had mixed luck. Some work flawlessly, others don't work at all without the google apps.
It would be awesome to see Mozilla's location service [0] integrated into Cyanogen to replace the google location services (which are of course disabled if you don't install google apps).