Almost all Google products except maybe adwords and adsense are based on the Freemium models, i.e. almost all services listed on: http://www.google.com/intl/en/services/
Actually the list is quite big and there is an endless list of companies that have been implementing this model for years if not over a decade.
Hotmail/Yahoo Mail have had the freemium model for years. Gmail was the game changer, but it is also on the freemium model since feb 2007
Almost all freelancing sites offer a freemium service, I think elance was among the first to start giving free monthly credits.
Actually if you go back to the days of the early alternatives of Windows Media Player etc too all the alternatives used to be Freemium in a sense, for example Winamp/Winamp Pro.
Freemium itself has been around for much longer than the term!
do you have a single category of apps in mind when you refer to freemium? That may help get more accurate examples!