I think that this might be "W.E.I.R.D. World" (1995).
That certainly sounds like it from the description on IMDb. Thanks Andrew, you are the undisputed king of obscure movies!
Too obscure to even have a DVD or VHS release unfortunately - I guess I'll just have to make do with my memories