How I would do it without, or with minimum use of mod_rewrite.
It will take some work, hard to say without knowing more about your setup.
First off I would change the schema in the DB.
- Backup the table ( call it - moviesas i don't know what you call it) - always make a backup.
 
- Output the table schema:
   - SHOW CREATE TABLE movies
 
- Modify the table schema
   add our new column - slugadd a unique index for the column
   change table name to 'tmp_movies'
 
- Write PHP script to copy the records from old table to new table
   patch missing slug (maybe the title lowercase with - in place of spaces)
   would have to account for possible duplicate slugs. 
- DROP the orignal table, and rename the tmp table to - movie
 
Now your DB is fixed.
- Change how you look up the pages, from using an id etc. to using the slug. 
- Change how you add new movies to create a slug. 
- Add one simple rewrite rule to replace the new way you look up movies.  
Something like  ( i'm just guessing at the htaccess)
   //type1  (URI)
   www.example.com/index.php/movies/slug  //typical url
   ^movies/([^/]*) index.php/movies/$1 [L]  //htaccess
   www.example.com/movies/slug  //re-written url
   -------------------------------------------------------------
   //type2  (Query)
   www.example.com/index.php?page=movies&slug=slug  //typical url
   ^movies/([^/]*) /index.php?page=movies&slug=$1 [L] //htaccess
   www.example.com/movies/slug  //re-written url
See your issue right now is you probably don't have much more then the ID in your url. Like:  
   www.example.com/movies/index.php?movie_id=2034
You need something in there with more appeal like this
   www.example.com/movies/murder-on-the-orient-express 
And the only way to go from this movie_id=2034 to murder-on-the-orient-express is to probably rewrite each one manually ( which is ridiculous )or add that something you are missing.
Hope that helps.