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?
Yes. Cataclysm is required to train archaeology. The trainers will have nothing to teach you if your account does not have Cataclysm enabled.
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.