Database on a different server?

In theory – yes.
Although be aware, most host do NOT allow access to their database from outside. So, you should clarify this with the host where the DB is.

I’m currently working with a WordPress install that has the database on an entirely different server. The Pro’s: It’s much faster. The Con’s: I can’t seem to solve the permalink issue. Works fine set to permalink default, once i try to implement the category/postname structure I get the old 404 error.

Once I find the solution I’ll post it here. Unless someone beats me to it.

Where the database is located has no bearing on permalinks.

If “pretty” permalinks give you a 404 error, then you’re either a) not using Apache or b) it can’t create the .htaccess and you need to do it manually or c) your host doesn’t support mod_rewrite.