There were, for want of a better word, large bodies of mercenaries in the early 1800s, starting with the King's German Legion. The Royal Navy was hiring kroomen (Kru from West Africa) already AFAIR, and its regular crews included men from all over the world. I am not sure about the status of Napoleon's Polish lancers - were they an allied unit or Poles in French service individually?
What you make of the various ethnic units raised by other combatants is questionable (are cossacks mercenaries? Hungarian hussars? Croat light infantry? They serve for pay and loot in the army of a warlord, so they're certainly not soldiers - warriors may be more appropriate). Colonial troops certainly qualify in many instances.
The majority of troops were regular (often conscript) soldiers, but the mercenary tradition was far from dead yet. Just a few decades later, Louis Philippe would create a Foreign Legion for which he saw some use and at least no insurmountable problems.