What about exporting table by table from your database? Or are your records all in one big table?
Did you try dumping as a CSV file? Although I think the PHP limits will still apply.
Can you create short PHP scripts to run on your database and just select so many records each time to an export file. Then when your have four or five exported data files representing your big database you can import them all back in a file at a time.
Ah you cannot run PHP scripts!
Cut and Paste using Browse?
Cannot you ask the admins at the host to run the command line dump for your database and plonk it somewhere for you. Perhaps if you were really nice and apologetic to them etc.
Is it a cPanel host?
Opinions are my own views, not DreamHosts'.
I am NOT a DreamHost employee OK!! :@
You act on my advice at your own risk!