Bien que rare, c’est grammaticalement correct. Il s’agit un conditionnel passé surcomposé.

Questions de langue – Temps surcomposés – Académie française:

Tout aussi rares sont les autres temps : conditionnel passé surcomposé (quand elle aurait eu fait cela ; quand elle aurait été partie)

j’aurais eu tôt fait de lui demander sa main.

est équivalent à:

je lui aurais aussitôt demandé sa main

Une expression idiomatique:
Avoir tôt fait de + inf. Ne pas mettre longtemps à. Synon. usuel avoir vite* fait de (This is from the CNRTL site)/

To not take long to do something, to quickly do something.

To change the tense of the expression, you work with AVOIR and leave “tôt fait de” unchanged.