I don’t know where it came from, but what I can tell you is:
1/ It’s not restricted to big or deal. It’s part of a general class of “adjective_of_degree of a noun” phrases. He’s not so good of a guy. I wasn’t expecting that small of a fee. It just shows us how dumb of a man he is.
2/ It seems to be frowned upon by scholars, but many regular folks prefer it.
3/ It is similar to some more accepted forms, e.g. not many people would tut-tut at “that much of a deal”.
4/ There appears to be no mention of this form in the OED’s entry for “of”, which is where I would expect it to be covered.
5/ The common view seems to be that this form originated in the USA.
6/ Here are some early examples I found using Google Books.
December 1850 Duffy’s Fireside Magazine (an Irish publication), in a story called Adventures of an Irish Giant “by the late Gerald Griffin”.
that big of a squall you wouldn’t hear outside her lips from one end o’ the week to th’ other
1890 Grip magazine (a Canadian publication)
“Say, mister, how big of a hole is through that wire”
1894 Carlotta’s Intended by Ruth McEnery Stuart (an American author)
I’m jest that big of a dummy
Note that in each of these early cases, this form appears in direct quotation of a fictional character. It is reasonable to think that the term was in spoken use for some time before anyone recorded it in print. Also note that the similar forms using other adjectives ("small of a”, “long of a”, “great of a” etc) don’t start popping up until the mid 20th century, so perhaps “big of a” really was the first in this class.