Hey MattyC,
Teaching is a very rewarding field and working with kids is truly a lot of fun! However, like everything else, it does have its challenges so I think it is a great idea to do a stint TESL first. In my opinion, entering the field of teaching from the workforce is a big advantage as you will bring some real-world experiences into the classroom. Kids love that. Additionally, if you take a TESL course and teach abroad for a while, that experience will be very rewarding for you in addition to giving you the insight that will be helpful in deciding if you want a teaching a career or not. I took an on-line TESL course years ago and liked it a lot. There are many TESL courses to choose from and its pretty simple process.
In terms of going overseas, there are many cool places to go... I have friends who went to Dubai and loved it so much they spent years there! One never even returned! I have other friends went to various places in Asia and they all found that very rewarding. Have fun researching where you want to go!
When you come back, there are many education programs to choose from. One of the best in my opinion is at the University of Lethbridge. They do more practical classroom work and graduates from there love the program. The University of Calgary also has a good program as does UBC. In terms of what to major in, if you have a propensity for math or science, I would HIGHLY recommend that. These teaching jobs are always the highest demand jobs as there are just not enough people that take the math/science route and go into (or stay in) teaching. Teaching technology is also a great idea so while you are abroad, maybe take an online course on coding if you can. The demand for technologically literate teachers is growing rapidly! There are a lot of free coding classes on edX from highly credible universities (Berkely, Harvard...). See
https://www.edx.org/
Best of luck to you!