My initial idea was to stick a Wi-Fi dongle into HP 3800 usb port, but is it going to work? This is not the network version (HP 3800n). Is it possible to turn it somehow into a wifi printer? I need to print from Linux and Android
You can't simply plug in a normal USB dongle. The printer's software won't recognise what is going on.
What you're going to need is a "Wireless USB Printer Adapter". HP will sell you their own product for this; just make sure that when you purchase one, it doesn't have compatibility issues with any of your network hardware.
You'll find hundreds of products by just typing "Wireless USB Printer Adapter" in google. Take a pick!