I just saw this thing today! I was WAR 7/MNK 3 and it was a Decent Challenge to me, so I believe it should be around Lvl 6 or 7! Didn´t take a Photo...
He was there when a High Lvl Player was fishing at the top most part of Cheval River. The one where you get the Blessed...for the Quest in the Sandy Cathedral! So I don´t know if the High Lvl Player was fishing him, or if he just popped there...