If you installed apache from your distribution then it almost certainly included mod_rewrite, it's just not being loaded. If you're on a debian-based distribution use
a2enmod rewrite to enable it, otherwise you'll need to find the
LoadModule rewrite_module /usr/lib/apache2/modules/mod_rewrite.so
(or something similar) line in your httpd.conf file and uncomment it.
If you built apache by hand, then assuming you also built mod_rewrite as a module, the httpd.conf fix applies to you, but if you didn't build mod_rewrite into apache and didn't build it as a module, you're going to have to recompile.