How to estimate if goods are complementary or substitutes when one good is always offered for free?
One answer is to try to find variation in the non-pecuniary price of the free good. Here is a famous example from estimating demand for public parks:

In 1949, Harold Hotelling wrote a letter to the National Park Service,
outlining a method where the park visitor’s round trip distance could
be used to proxy the recreation trip price, so that consumer’s surplus
estimates might be recovered. The idea was to obtain the net benefit
for outdoor recreation for a particular geographic area. The CVM
method was suggested in the same year in an article by
Ciriacy-Wantrup, although the first actual application of the method
(to deer hunting in Maine) was by Robert Davis in his Harvard PhD
dissertation, in 1963.

The new economics of outdoor recreation
Hanley, N. ;  Shaw, W. S ;  Wright, R. E. (2003)
Chapter free here
It seems like something very similar is possible here. For example, say you were asking about complementaries between the radio (which is free) and cars (which are not). You could look at hard of hearing people, and how demand changed for the radio as more and more expensive equipment is required to listen to the radio.
Or consider evaluating if public schools and Disney World are complements or substitutes. Using distance from school as a proxy for the variation in the cost of &quot;consuming&quot; school, you could use that variation to trace out the cross-price elasticity of Disney with respect to school.