I'm having some trouble parsing the implications of all the job titles that get thrown around in academia. Does someone whose job title is just "Professor" necessarily have tenure, or are there nontenured full professors?
It depends on the institution whether it is even possible, in principle, to have nontenured full professors. At some institutions, being a full professor automatically means you have tenure. At other places, it is merely overwhelmingly likely that a full professor will have tenure.
Any case where somebody is a full professor but does not have tenure is likely to be a bit odd. In my department, there have been, in the last twenty years, two people who had the title of "professor" without being tenured. One of them was a senior person who the department hired, but for some reason they could not hire this person directly with tenure. Instead, they were hired as an untenured full professor, with a two year tenure clock. They turned in their tenure file after one year and got tenure with no problem. The other person is a former tenured full professor (and department head), who moved to an entirely soft money position. He was allowed to keep the title "professor," but he is no longer tenured, with his position coming up for review every three years.
There are three things you need to consider.
First is that "professor" is often used in an informal way for just about any instructor on the regular staff, as opposed to its formal meaning. In material printed/published by a university, however, it is more likely that it is used to mean "full professor". But otherwise, it could mean a lot of things.
Second, there are some institutions, not many, that don't offer tenure to anyone but still have traditional titles for the faculty. People may work on fixed term renewal contracts in such places. I don't know that such places are highly ranked, however.
Third, a person might be hired from another institution with the rank of full professor but still need to go through a probationary period before tenure is given. This might be two or three years. The purpose of it (possibly) is that the hiring is done by the administration, but tenure is offered "on recommendation of the faculty." Thus other faculty have a chance to evaluate the new person.
I have examples of all of these in use.
While Buzz's answer is absolutely great, let me add that "tenure" does only mean you cannot be fired, but not that you are payed by the university: see Consequences for a tenured person of not getting grants where GEdgar gives in his answer (and a commentator too) examples of US professors which are tenured but whose contract does not say that they have to be paid by the university.
(I wanted to add this because by "tenured" I think about having the "freedom of research" which does arguably not exist in such examples.)