Early Gameplay Changes

You can't make furnaces without iron.

Sorry.
So, you ask,

How do I get iron if I need iron to make the furnace to smelt iron?

To get iron now, throw an iron ore into lava to obtain 'charred' iron ingots. Do this 4 times and you will be able to make a furnace with 4 cobblestone and those ingots.
For more changed recipes, head to the FAQ's changed recipes question.