you could follow a scheme where for most pages you do:
/blah/subset-of-blah
so that would cover the pages where there was no query string
or you can do a halfway friendly version where you use your page id something like
/blah/subset-of-blah/27
(the entire text can then be thrown away if you only need the page id..
that might work well on a site where you know you cannot logically enforce unique page names)
...that's so you can think about what might work best.
THEN you can add your query string - you can just add it like this:
blah/moreblah/param1=77¶m2=88
so you do not have to split each parameter into its own slashed space
then in htaccess rewrite you channel that third parameter (in this case the entire query part
"param1=77¶m2=88") into a traditional query variable, call it $qstring
then you can explode this or otherwise grab the param values in PHP
..you are correct it may need all old style urls to be changed within the site (for consistency and google you should change all to one format ) - BUT your old standard urls may continue to work - it depends on your site code and structure