The cheapest ways to try cross country skiing are borrowing equipment, yard sale equipment, craigslist, or rentals. If you like it, and rent frequently, that stops being cheap.
If you make friends who run or are otherwise active, ask around, and someone might have a spare set of skis and poles they can lend you - you can find them for a few dollars at yard sales sometimes, and some skiers pick them up as spares or loaners (This is why I've got 3 sets of skis for 1 set of legs). Then you'll just need to buy boots.
Places to ski:
Easiest: flat ground, groomed trails, golf courses, snowmobile tracks.
Harder: Slopes, or anything with virgin snow (snow with no tracks). With virgin snow, it's generally best to go with one or more buddies who can trade off in trail breaking, or go for very short trips.
Hardest: Very hilly or mountainous, especially with virgin snow.
If you're sticking to flat terrain or groomed trails, you can pretty much get out and go with little or no instruction (depending on your tolerance for falling and being awkward). I don't know about Quebec specifically, but in Massachusetts, some golf courses rent cross country skis in the winter, and groom tracks for skiers to use. Other courses don't make it official, but still allow skiers on their grounds. Depending on what you are looking for, a season's pass to a local golf course may satisfy your need for exercise at a reasonable cost. The disadvantage would be that you could only ski at that location.
If you want harder terrain, it would be worth either taking a lesson, or going out with a friend who skis. Going straight is easy to figure out, as long as you don't care about being the most efficient possible. Turns and hills are a little harder. If saving money is most important, and you don't have any skiing friends, you can learn technique from books and videos without much trouble.