Both cooling fans are supposed to turn on in low speed mode when the engine temperature reaches 220 degrees and around 230 degrees turn on in high speed when the A/C is off. With A/C off what does your temperature gauge read. Is it over the half mark? Initially with ignition to OFF if you disconnect the ECT - engine coolant temperature sending unit and then start engine both fans turn on in approximately 5 seconds so the cooling fan relays may be good so you may be wasting time there. You may have another problem or even a PCM issue.
Also, has the engine coolant ever been replaced and the cooling system flushed? I hope you don't still have the original Dex-cool coolant since it is only good for 5 years or 150K miles, whichever comes first.
As to ECM/PCM module flashing or re-programming by those vendors on EBay that is common practice and reliable. Part of the cost of the ECM so normally they are good deals versus buying new and having a GM dealer flash it. I've never had one (dealership) do it for free and the charge can range from $40-$80 at the stealership. All they need is the VIN number and year. Also companies like DHP re-program PCM modules but I would not go that route unless you plan on modifying your Alero. See link below.
Click here
Note: With a DHP PCM the cooling fans turn on at 180 degrees so you never have to worry about temperature creep up with the A/C off.
Also, since the cooling fans turn on with A/C on then you are wasting your time with changing out the cooling fan relays.