As mentioned on the Medium Trust page, for Data access to work in Medium trust the ADO provider for it must be in the GAC.
So you can either use MS SQL or convince your host to install the MySql Connector on the sever which would put it in the GAC.
The latest mojoPortal from svn turnk has the new version of MySql Connector and I've been told it works in medium trust without being in the GAC but not sure its true as I haven't tested that myself. You can try replacing the MySql.Data.dll in your bin folder with version 126.96.36.199 which you can download from the MySql site or get from svn trunk. However, I think if it does work it will require re-compiling the solution.
The current relase version doesn't have the new MySql Connector.
Hope it helps,