We use the Future Perfect to make predictions about actions which we expect to be completed before a particular time in the future:
I'll have finished this assignment by Friday.
When I finish this book, it means I'll have read all of her books.
He'll have had the operation by July and should be a lot fitter then.
We usually use a time adverb/phrase (e.g. soon, by then, within the next week etc.) with this kind of prediction. The times can be very close to "now".
So, by the time we get there, he'll have been gone is perfectly correct. You use the time phrase "by the time we get there", and you point out that something will have happened by the time you arrive. It makes even more sense if there is more information/context (e.g. By the time we get there, he'll have been gone for 3 hours).
I feel that "he'll have been gone" is more correct than "he'll be gone" in this particular context. But I'd use the Future Simple with some other time clause, not "by". For example, When we get there, he'll be gone.