Fossil Fuels
You say you don't have a lot of oil or natural gas, but you're limiting your fuel sources. You can get natural gas from coal via the coal gas reaction. That's the source of the gas used for gaslight in Victorian times.
Other sources of energy
Pine Trees
Pine resin can be refined into turpentine, which—as @egor045 mentioned—can be used for fuel. With all those trees, you've got yourself a massive potential source of wood alcohol (methanol), another potential fuel. Lots of pines means lots of pine nuts, which can be used to produce pine nut oil, as well as delicious, delicious, pesto. That's another source of fuel (the oil, not the pesto).
Other plants
Diesel's first engines were designed to run on peanut oil. The Model T's engine can run on ethanol. Distillation of alcohol could be done using pines as a fuel, or, if the climate gets cold enough, by freeze distillation. Get yourself some high-proof hooch, spike it with methanol to keep people from drinking it (drunk driving is bad) and you've got yourself a great power source for an internal combustion engine. As for oil for diesel-style engines, why not use an existing plant that is high in oil like sunflowers, rapeseed, or peanuts. You could invent your own plant, too. Make it high in usable oil, but have that oil be difficult to extract or useless without some piece of technology or recent discovery and you'll have yourself the foundation of an oil economy.
Hydropower and wind power
The Industrial revolution didn't start with steam power. It started with water and wind power. Mills and factories ran on waterwheels long before people discovered that lightning wasn't Zeus throwing another temper tantrum. It was windmills that pumped out the Zuiderzee. Electricity generated from these methods could be used to power things directly, or in the manufacture of something (e.g. methane) that will work as a fuel.
Hydrogen
With 19th century technology, you've got the ability to use the electricity generated in some other way (whether or not that way is detailed here) to electrolyze water. That gets you hydrogen and oxygen. The oxygen can be sold off to people exploring the ocean or really tall mountains. The hydrogen burns, and will do so quite energetically, but might be better used in the Sabatier reaction to produce methane (i.e. natural gas).