Modelling of rent prices - which interpolation method to use?

The idea is good but the proposed implementation may be too simplistic to be credible. Rents are a property of economic systems. Besides being influenced by location, they are related to other economic variables in important ways: state of the local (and national) economy, local housing prices, availability of capital, employment rates, etc. To do a good job you need an econometric model. It might benefit from having some spatial lag terms, but before such complications are considered you need to include many of these economic covariates.

Having said that, your ability to succeed depends on the relationships between the data you do have and the rents you want to predict. If your data are a representative sample of the entire country and are geographically dispersed--think of houses as raisins on a cookie and you have data about every other raisin in the cookie--then a relatively simple model might suffice. If your data are geographically focused--maybe you have information about raisins on the right side of the cookie and you want to make predictions for the raisins on the left side--then the problem is a more difficult one.

A good point of departure would be to fit a conventional linear econometric model of rents to household characteristics and gross spatial characteristics (such as state or county tax policies), compute the residuals, and begin exploring the residuals spatially (using variography, spatial kernel smooths, etc) to capture the geographic effects.

Suitable software is available as add-ons to R.

As a very gentle introduction to topics on spatial regression I would highly recommend checking out the GeoDa workbook (chapters 22 to 25 will be of most interest). Even if you don't want to use the software it is a very comprehensive overview of spatial regression.

Will the built in regression functions in ArcMap handle that much data (not that any software would have a difficult time with that many points?)

I've seen similar work done for house prices using hedonic modelling. See http://scholar.google.com/scholar?hl=en&q=hedonic+price+geography for examples.