It was actually not very common before Jesus arrived on the scene for God to be referred to Father. Baker's Evangelical Dictionary of Biblical Theology notes:
This portrayal, however, is surprisingly rare in the Old Testament. There God is specifically called the Father of the nation of Israel ( Deut 32:6 ; Isa 63:16 ; [twice] 64:8 ; Jeremiah 3:4 Jeremiah 3:19 ; 31:9 ; Mal 1:6 ; 2:10 ) or the Father of certain individuals ( 2 Sam 7:14 ; 1 Chron 17:13 ; 22:10 ; 28:6 ; Psalm 68:5 ; 89:26 ) only fifteen times. (At times the father imagery is present although the term "Father" is not used [ Exod 4:22-23 ; Deut 1:31 ; 8:5 ; 14:1 ; Psalm 103:13 ; Jer 3:22 ; 31:20 ; Hosea 11:1-4 ; Mal 3:17 ]). This metaphor for God may have been avoided in the Old Testament due to its frequent use in the ancient Near East where it was used in various fertility religions and carried heavy sexual overtones
The teaching of the Fatherhood of God takes a decided turn with Jesus, for "Father" was his favorite term for addressing God. It appears on his lips some sixty-five times in the Synoptic Gospels and over one hundred times in John.
Heaven however was another matter an God was typically regarded as dwelling there. This is a theme common throughout Middle-Eastern cultures in some of the earliest writings, with Heaven being regarded as in opposition to the Underworld.
This is obvious from Genesis 11 (the story of the Tower of Babel) and Genesis 19 where is says in V 24:
Then the Lord rained down burning sulfur on Sodom and Gomorrah—from the Lord out of the heavens.
Genesis 21 and 22 has God calling to Hagar and Abraham from Heaven. In 24:7 Abraham regards him as "God of heaven" and Genesis 28 has Joseph dreaming of a stairway to Heaven where Joseph remarks "How awesome is this place! This is none other than the house of God; this is the gate of heaven."
Joshua 2:11 says
for the Lord your God is God in heaven above and on the earth below.
And 2 Samuel 22:14 has the LORD thundering from Heaven
Ezra makes frequent use of the term "God of Heaven" (6:9-10; 7.12; 7:21; 7:23) and Nehemiah uses this term in 1:5, 2:4; 2:20; and Chapter 9)
The Psalmist describes God as "Enthroned in Heaven" in 2:4 and says in 14:2 that
The Lord looks down from heaven on all mankind to see if there are any who understand, any who seek God.
Isaiah 38:14, Isaiah looks to the heavens to call out to God and begs God to "Look down from heaven and see, from your lofty throne" in 63:15 and Isaiah 66:1 says
This is what the Lord says: “Heaven is my throne, and the earth is my footstool. Where is the house you will build for me? Where will my resting place be?
Lamentations 3 places God in heaven saying
Let us lift up our hearts and our hands to God in heaven, (Vs. 31)
until the Lord looks down from heaven and sees. (Vs. 50)
And Ezekiel has a vision in which he sees God in heaven. Daniel 2 repeatedly calls God the "God of Heaven" and in 4 a message from God comes "down from heaven"
Amos 9:6 says
he builds his lofty palace in the heavens and sets its foundation on the earth; he calls for the waters of the sea and pours them out over the face of the land— the Lord is his name.
So as you can see from the above, the idea that God was "in heaven" has a long tradition and this was typically regarded as His dwelling and domain.