I believe that Mary (Davis) Randolph's parents were most likely James and Rachel Davis as per the following records that show them in Mifflin/Juniata Co., PA during the same time period as John and Mary Randolph:
From "Records of the Tuscarora Valley - 1794-1828):
--On April 15, 1798 Rev. Mr. Davis from Delaware State preached
--Saturday, May 26, 1798 Rev. James Davis concluded the church meeting in Tuscarora Valley with prayer.
--Saturday, June 9, 1798 Received Rev. Davis and wife Rachel by letter and appointed him as our pastor.
--Saturday, August 16, 1806 - Tuscarora Valley - Elder James Davis and Rachel Davis - obtained letters of Dismision for this church.
--October 22, 1820 - Brother Davis from Mill Creek (Huntingdon Co.) supposed to appear service at Baptist Church, Milford Twp., Mifflin County, Pa.(no show). (This congregation at Milford Twp. seemed to meet in homes and other places like Thompsontown and Mifflintown, etc.)
--Saturday, June 19, 1827 - Received into fellowship and communion - Mary Reynolds and Mary Randolph
History of Huntingdon and Blair Counties, Pennsylvania by J. Simpson Africa Philadelphia, PA: Louis H. Everts, 1883, pp. 217-228.
Mill Creek Baptist Church. - As early as 1790 the Rev. Samuel Lane preached in this locality, which was probably regarded as an out-station of the Baptist Church in Trough Creek Valley, of which he was the pastor....The constituent members were James Hampson, Nathan Gorsuch, Ann Hall, Mary Hampson, Temperence Brown, Lydia Plowman, Samuel Lane, James Davis, Daniel Brown, Rachel Kelly and Rachel Davis. ....Mill Creek Church was admitted into the Baltimore Association in 1817...The pastors of the church from its organization to the present have been as follows:
The Rev. Samuel Lane, for a number of years, probably until his death, about 1812...After his decease there does not appear to have been a regular preacher until some time about 1820, when the Rev. J. Davis, who had served in the Revolution, was reported as the pastor.
In my research I have not found any documentation that would support your theory of connection to the FitzRandolphs of New Salem, WVA.The only connection of this family to John and Mary (Davis) Randolph of Trumbull/Mahoning Co., Ohio would be by the FitzRandolph DNA making them, more likely, distant relatives.Jonathan and Mary (Davis) FitzRandolph's families had already settled Harrison Co., (West) Virginia (abt. 1790) and they were married there in 1798.John & Mary Randolph were living in Mifflin Co., PA during that time and probably did not leave PA until after 1827.