Using category slug in add_rewrite rule

You should be able to use

category_name=$matches[1]

instead of

cat=$matches[1]

Generally speaking, you can use any built-in public query variable and custom ones, after some additional work, see the add_rewrite_rule() codex entry for more information.