Can I build a deck from reclaimed 2x4's?
How old is the wood? If we're talking 70 years or so, definitely don't burn that stuff as that'd be old growth wood which you just can't get anymore (easily). I'd even have a hunch that a 70 year old 2x4 might carry as much of a load if not more than a modern cheap pine 2x6.

All that said, as you state, it's not treated lumber. Unless it is cedar, you likely won't get much life out of it as a decking material--unless you have plans to refinish it each and every year. 

The 2x4 also wouldn't make for a sufficient floor joist, so you'd have to use new structural lumber for that anyways. 

If it's old lumber, I'd consider saving it for another construction project, or donate it to your local re-use center or habitat for humanity. If it's not old lumber, I'd use it for the fire pit.