Linode uses Xen, which means that you not only have an app; you have a whole operating system, complete with kernel and base libraries. The attack comes from your system, so it is completely in your jurisdiction. The attacker entered your system in some way, but once there, if he is at least half competent, he used a rootkit to transform his break-in into a permanent installation. The downside of it is that a rootkitted system will not show up from the inside of the system: the kernel would have been infected and will not show the attack process from the attackers.
(I am using here the assumption that once the attacker entered, he could escalate his rights into root level -- that's the prudent assumption, because operating systems are rarely rock solid against local attackers.)
This implies that your system should be wiped out and reinstalled from scratch; it has been compromised and can no longer be trusted. At that point, you would have two goals:
- Understand how the attacker came in, so that he won't do it again on the newly reinstalled system.
- Convince the Linode people that you are a victim, not an accomplice.
For the first point, this is a matter of analysis of all the logs and other traces that can be found in your system. So before scraping it, take a full copy of it (preferably, a byte-by-byte copy of its virtual hard disk) for ulterior analysis. But remember that if the attacker is reasonably good, he covered his tracks (that's what rootkits are for). Also, some auditing of your application code would be in order: the attacker entered in some way through one of the externally accessible services of your server, which includes your application. Another possibility is that the attacker guessed your SSH account password (after all, you know that this attacker does run brute-force attacks on SSH logins): on your new system, use a new, bigger, more random password (don't type it on your current system ! It is compromised, thus possibly grabbing password changes on-the-fly).
For the second point, this is a matter of trust and human relationships. You cannot prove that you are not the attacker; but the Linode people know that hijacked systems are an unfortunately common reality. Just exercise due diligence, such as reinstalling the system from scratch: going through that tedious task will go a long way towards establishing your good faith in that matter.