I know MD5 is no longer secure, but is there an algorithm running in polynomial time to find preimages of a given hash, or is it just bruteforce?
You won't be able to find a preimage for MD5.
The best preimage attack against MD5 has a complexity of 2123.4 and requires 245 × 11 words of memory. This is faster than brute force, which has a complexity of 2128, but still isn't practical. The only attack that can be realistically performed against MD5 is collision and chosen-prefix collision.
Even MD4 isn't particularly vulnerable to preimages, with its best preimage attack requiring 299.7 operations and 255 memory, finding a preimage of at least 250 blocks! Preimage attacks are hard.