I'll be interested to see what other people suggest. I'm sure there are functions for this in zelig or caret.
The forecast package (Hyndman and Khandakar 2008) that you mention is very useful. See this paper for a discussion/example (these how applications: here and here). For instance, it contains a function auto.arima() that performs a search over a set of models. Kleiber and Zeilis "Applied Econometrics with R" have some nice examples of how to do this, so I recommend that book. Here's an example of the usage:
> fit <- auto.arima(WWWusage)
> fit
Series: WWWusage
ARIMA(1,1,1)
Call: auto.arima(x = WWWusage)
Coefficients:
ar1 ma1
0.6504 0.5256
s.e. 0.0842 0.0896
sigma^2 estimated as 9.793: log likelihood = -254.15
AIC = 514.3 AICc = 514.55 BIC = 522.08
If you want to try something different, the accuracy package has some useful functionality which can be used. For instance, look at the modelsCompare function. This should work with time series models as well.
I think that AIC or BIC are generally the most widely accepted statistics. Venables and Ripley "Modern Applied Statistics with S" (see the MASS package) has a lot of material on "automated model selection". I also recommend that book.
Lastly, the tsDyn package also contains functions to help with selection for non-linear models (see the excellent vignette on the subject). You can use the selectSETAR, selectLSTAR, and selectNNET functions.