Could the Edain have a Gondor kingdom during the First Age?
 

If all the houses of the Edain reunited, could they have been many enough with skills to build a kingdom similar to Gondor in the Beleriand?

Gondor was built with some of the knowledge and skill of Numenor, which the Edain of the First Age didn't have. A First Age Edain kingdom would likely look very different than the late Second Age Gondor.

How different? More like Rohan and Dale?

The Beorians had pledged themselves to the service of the House of Finarfin; that of Marach/Hador became lords of Dor-Lomin as vassals of the House of Fingolfin. The Haladin had no interest in being ruled by anyone but themselves.

So, no.