check out
http://www.hotscripts.com/PHP/Script...rds/index.html
there are quite a bit of different php message boards listed there, some require mysql but some dont. there are non-free boards and there are some free ones as well
you seem to have an interesting host. i dont see why they would allow php but not mysql or some other database. you should still try to convince them otherwise, using a database its quite to your advantage
--
another thing you might do is put mysql on some other computer somewhere, i'm not sure about php features and modules but i know the perl dbi module is capable of connecting to remote mysql servers (not just the webserver itself). i think mysql is a service in general so i bet the php stuffs can do this also
it would allow you to run a mysql powered database but if the mysql server isnt in a local area of the webserver, the site might be kind of slow...
good luck