Did everyone check DARE D-H (Volume II)? "FRY BREAD See FRIED BREAD 1,2."
FRIED BREAD is on pages 573-574. The earliest citation by far is this
one:
1836 (1930) Phelps _Diary_ 228 IL, The fourth day of July I gave a feast to
all the squaws, we boiled corn and had some fried bread, a favorite dish with
them.
The next citation is 1895.