What does impedance control on a PCB mean
I understand that when the electrical length is less than 1/10 of the trace length I would have to go in for impedance matching.


You have this backwards, the common rule is to use impedance control when the electrical length of the trace is more than 1/10 of a wavelength at the frequency of interest. (Like Rolf points out in his answer, the "frequency of interest" is more related to the rise and fall times of a digital signal than to the data rate)


  So when a factory says it does impedance control , does it mean that they do that kind of a stack up? 


It means they can control the thickness of the dielectric layer and the width of the trace with close enough tolerance to guarantee impedance matching to within some specified limits (often +/- 10%)

Also, like the other answer points out, they should have test equipment to allow them to verify the boards they produce.


  What does it mean when a factory says they will not do impedance control?


It means they can't control the geometry closely enough to guarantee the impedance is within tolerance.


  Is it that they cannot do that stackup? 


No the stackup doesn't change, it's how well controlled the geometry is.


  If so , sticking to a normal 4 layer board stack is sufficient?


No, you need to control the geometry well to be able to get the required impedance.


  What is th main FR4 specification that determines the impedance?


Dielectric constant, often designated \$\epsilon_r\$ or \$D_k\$ is the critical material parameter. 

The thickness of the dielectric is also critical.


  Because right now I have a boards which has a stack up for 4 layers with thickness of each layer. DO I have to send this stack up to every PCB house and ask if they do this? 


You just have to send it to one board shop that knows how to do impedance control, or 2 or 3 if you want to get competitive bids.

Many many board shops are capable of impedance control, including many of the modest-priced shops that advertise online. Only the most low-cost shops (and probably most of the hobbyist shops that charge by the square centimeter and combine your design with others) can't do it.


  How do I build these boards?


Send the manufacturing files to a board shop with capabilities that match your requirements, and pay them to build them for you.