Is using URL rewritting instead of multiple parameters the only way to make sure all pages are indexed by Google?

I do not believe Google says. It used to be true that test_param_1.html was better than index.php?module=test&param=1 but I do not believe that is the case anymore for Google.

However, if your 2 examples pages are very similar in content then you will want to use a rel="canonical" on them so Google knows which one is the master. Otherwise your pagerank will be split between the 2.

No, URL rewriting has no positive influence on crawling or indexing; oftentimes it can even have a negative effect. For instance, many websites embed all parameters as well as plain text (eg the "title") in the URL when rewriting them, creating pages with many possible URLs (we often even see session-IDs rewritten in URLs...).

We did a blog post on this at http://googlewebmastercentral.blogspot.com/2008/09/dynamic-urls-vs-static-urls.html

Personally, unless you are absolutely certain that you are able to set it up absolutely correct and that it has a measurable impact on user satisfaction (ignore the search engines for this!), then I would strongly recommend not rewriting URLs at all. We see so many big problems with sites that use URL rewriting that you should really think quite a lot about this before going down that road -- and certainly never do it just for an assumed search engine advantage.