Just because the "From:" in an email says your email address, doesn't mean it came from you. In fact, it most-likely did not. It's trivially easy to forge the "From:" field when sending emails, and spammers usually do this intentionally.
One common scenario is for a PC to get infected with malware that uses it as a spam relay. The infected PC is scanned for all address books and the addresses found are then used to randomly fill in the "From:" field as well as the "To:" fields so that the spam appears to come within that person's circle of contacts, giving it a greater chance of being opened and read.
So likely it's not your PC but the PC of someone you once emailed or who emailed you.
Any "professional" who took 30 seconds looking at the full headers of the spam email could've easily figured out whether it was actually coming from your computer or not. I'd suggest finding a better place to take your PC.
To answer your general question, "Does anyone know if you could get a malware rootkit on your android phone?" the answer is "yes", if it was rooted... however I know of no malware for Android that uses it as a spam relay. Desktop Windows PCs are the pretty much the exclusive target.