If you've got a pork tenderloin and not a pork loin, and you really want to try something new, you could try to do a roulade. If you're not familiar with roulade, it's basically where you cut or pound your meat such that it lays flat and wide like a book or a large sheet of paper (not that thin though). WHat you do is lay your stuffing over the expanse of your pounded meat, and then roll it up tightly, tie it with butcher's twine, then cook it. I think it's normally a roasted dish, but there's no reason you couldn't do it on the BBQ, and no reason you couldn't smoke it.
Rosemary was mentioned as an herb to use, which I really agree with; I think it gos great with pork. I also think that, made well, a cranberry sauce would go well with it. What I think could be really killer is if you did rosemary cornbread for your roulade, and then after you tie it up, crust in in some cracked peppercorns. If you have any chicken glace or stock I would use that as a sauce base and use some kind berry with it, though I think some golden raisins or sultana raisins might really elevate the dish.
Wow, and now here you've got yourself quite a dish if you want to do it.