It's definately possible.
I've been running linux on my A4k for quite some time and it works very well.
As already stated you need a processor with a MMU and preferably an FPU as well. FPU-emulation doesn't quite do the trick even if you can make it run. The latest debian distro's doesn't work well at all without an FPU but if you get hold of the old RedHat it might work, haven't tried myself.
The only uptodate distro is Debian and it's almost on the same level as the i386 dist. The development is a little behind because of lack of m68k-based computers to do the compiling and testing, but there are a few people still on it. The Amiga bootdisks are probably in the fronline before the other m68k based systems.
Check Debian up
http://www.debian.org On my A4000/040/40 with CV64/3D and Ariadne-II it works very well. Though, X is rather slow at times. Mozilla works well but the waiting times are sometimes quite long.
If you can find it you can go for the old RedHat 5.1 port. It should still be avaliabe to buy cheaply. I checked the site where it once was downloadable but I can't find it there so I don't know if it's still avaliable online.
There was a 5.2 port as well but it never got quite finished to be called stable, but I compiled a CD from it so I have it and it never gave me any problems.
Though, it refuses to identify my harddrive now. Don't know exactly why that is, it might be that it doesn't recognise my 5 GB HD. I had a 2 GB when I ran that distro.
If you want to get hold of the RH5.1 or 5.2 CD's and can't find them just contact me and I'll see what I can do.
The downside with the old RH's is that there isn't any web browser that can handle modern webpages, but it's a LOT faster in X than the newer Debian dists are. I recommend a 060 to run Debian 3.0
Have fun!
