What are the longest half-lives we can detect experimentally? What stops us going further? Are we trying to?
are these walls hard? That is, can we plausibly measure longer half-lives?
No, the walls are not hard, and it is certainly possible to experimentally confirm longer half-lives by doing what the question says:
you will need either a lot of isotopically pure xenon or a long time of very efficient, background-free detection, or (probably) both.
That is, get a lot of, say, xenon (on the multi-ton scale, rather than the grams used in the question, in condensed phase) in an underground cavern, away from background radiation, look for signatures of the decay, count the number of decayed atoms, compare against the total number of atoms present, and infer a half-life from it. As of the writing of this answer (May 2019, some four years after the question), the record has indeed been upped from the ${}^{136}\mathrm{Xe}$ half-life by the XENON1T experiment, which used that method to confirm a much longer half-life for an isotope of xenon on the light end of the range $-$ ${}^{124}\rm Xe$, with a measured half-life of $1.8\times 10^{22}\:\mathrm y$. (Also discussed on this site here.)
Presumably there are similar searches going on with isotopes that have slightly longer half-lives, but they'll not be the easiest to find unless one works inside that community.
That said, these are not the longest half-lives that we can infer from indirect measurements. The tellurium-130 assignment by the Wolfram curated data looks fairly shaky upon closer inspection (and indeed most half-lives in this class probably have a fair degree of scatter and need to be researched carefully before they're taken without a grain of salt), but there's definitely literature describing half-lives on that timescale.
Specifically, the Wikipedia page on the isotopes of tellurium marks tellurium 128 as the longest known half-life at $2.2\times 10^{24}\:\rm y$, though without a clear literature assignment for where that figure comes from and how it was obtained. I'm not an expert in how you sift through this literature, so the best I could find (which is still pretty good) was the paper
Precise determination of relative and absolute ββ-decay rates of ${}^{128}\rm Te$ and ${}^{130}\rm Te$. T. Bernatowicz, et al. Phys. Rev. C 47, 806 (1993)
which pins the ${}^{128}\rm Te$ half-life at $7.7\times 10^{24}\:\rm y$. This is done through geophysical evidence, by doing precise mass spectroscopy to determine the relative abundances of the different isotopes of tellurium and of their gaseous decay products, together with radionuclide dating of the minerals that contain those isotopes (using other elements with better-established, shorter half-lives), which then enables a measurement of their relative half-life of the different isotopes; one then measures the shorter half-lives and infers the longer ones.