Now that Colombian citizens are exempted from the short-stay visa requirement for the Schengen area, the closest to the truth is scenario 1, with a few nuances. Your wife will then be able to use her 90 days to enter Germany and deal with the rest later. Before that, you were in something like scenario 2, except that the “spousal visa” is only a special type of Schengen short-stay visa (you would apply with the same form but with different requirements).
In any case, you, as a British citizen, do not apply for anything. You won't even get any document confirming that you are making use of your treaty rights (such a document, called a Freizügigkeitsbescheinigung, did exist a few years ago, but no more – another source of confusion). You simply have an implicit right to stay for as long as you want by virtue of the fact that you are working. You do have to register with the municipality within a week or two of settling in the country, a procedure that has no direct equivalent in the UK but is mandatory for everybody in Germany, including German citizens.
By contrast, your wife, as a Colombian citizen, does need to complete some additional formalities. Technically, she would not really apply for a “permit”. Instead she is required to get a “card” to which she is entitled, specifically an Aufenthaltskarte für Familienangehörige eines Unionsbürgers (the fact that it's called Aufenthaltskarte and not Aufenthaltserlaubnis is supposed to underline this distinction). But in practice she needs to fill in a form and submit it to the authorities together with some documents all the same. You, the British citizen, will have to document your situation (i.e. produce a work contract) when applying for your wife's card since she is only entitled to it because you are working and sponsoring her. Your wife will then get a plastic card documenting her status.
Now if you don't have a job after 90 days, you will need another solution to ensure that your wife has a right to live in Germany (legally, as long as she really qualifies for the card – i.e. she is the spouse of an EU citizen with a right of residence in Germany – she does not risk deportation but only a fine, even if she failed to apply for the residence card in a timely manner). One option to qualify even without looking for work is to show that you qualify for residence as an “economically non-active” EU citizen, which means showing you have enough money/income and health insurance for both of you.
This status (family member of an EU citizen, working or not) also gives your wife the right to work in Germany without any additional authorization.
Regarding the contradictions between different sources, it's important to realize that there are at least three very different situations here so people might mean different things when they talk about “spousal visas” or might not even realize how their situation differs from that of others:
- Spouses of German citizens
Spouses of other EU citizens with two sub-cases
2.1. The spouse is visa-exempt based on their citizenship, you can enter and sort things out later.
2.2. The spouse requires a visa to enter the Schengen area. Accompanying or joining an EU citizen should in principle make obtaining that visa simpler but it needs to be done from abroad.
Spouses of third-country nationals residing in Germany
Only info specifically about situation 2 applies to you and your family. It's typically the best one to be in, people in situation 1 and 3 generally have to apply for a visa from abroad, might have to prove they know some German, have enough income to support the family, etc. (and to make everything even more complex, there are special cases and exceptions in situation 1 and 3 as well) So if you are reading a blog post from the Indian wife of a US citizen or the American husband of a Japanese citizen or the Canadian spouse of a German citizen, those people are in fact in completely different situations, legally speaking (as a matter of fact, the rules that apply to you and your wife are defined in an entirely separate statute).
Info on europa.eu tends to be dependable but it sometime paints a somewhat rosy picture based on a strict reading of EU law, which some countries do not apply fully. Germany is however quite good in this regard so if you find a job and are able to document your marriage to their satisfaction (beware of potential translation, legalization, authentication, etc. requirements), I would not expect any complication.