With the new expansion out, do I need to have Cataclysm added to my account in order to go to an Archaeology trainer and start learning/using the new secondary skill?
The short answer is no you can not train without upgrading. One can only train Archaeology after one's account has been updated to Cataclyms. There isn't an screenshot that can be used as proof. However, proof can be found on page from the trustworthy fellows at WoW Head.