The sci.math discussions linked to above suggest that Andrew Granville suggested the problem in 1992 and that it was discussed as early as 1985.
I have in my notes:
T-Z predates Beal; see Frits Beukers, "The Diophantine equation $Ax^p+By^q=Cz^r$", Duke Math. J. 91:1 (1998), pp. 61-88.
This kind of informal documentation may be the best available, unfortunately.
Edit to expand on a comment:
On sci.math, Gerry Myerson wrote on Aug 22 2000:
Since Andrew Granville's contribution to the Western Number Theory problem list has come up in this discussion, I want to put it on record here. The December 1992 Western Number Theory meeting was held in Corvallis. The problem list was edited by Richard Guy and is dated 9 June 93. The relevant part of Problem 92:12 reads as follows.
92:12 (Andrew Granville) Find examples of
x^p + y^q = z^r with 1/p + 1/q + 1/r < 1 other than 2^3 +1^7 = 3^2 and 7^3 + 13^2 = 2^9. [Blair Kelly III gave 2^5 + 7^2 = 3^4 and Reese Scott 17^3 + 2^7 = 71^2.]
In Guy's write-up of the 1993 problems, dated 3 March 94, there is a comment about 92:12, wherein Granville agrees with the suggestion that it was intended that x, y and z be relatively prime, and gives 3^5 + 11^4 = 122^2 as another example. Peter Montgomery gave 5 larger examples found by Beukers & Zagier.