A linode 512 used to be a 256 a few years ago. In fact, if you go back far enough, I believe it started as a linode 64

It's not likely that Linode will consider anything smaller than this (probably because the profit margin gets too small). However, there are two things you can do to help reduce the cost from $19.95:
1) Pre-pay for 2 years. This gives you a 15% discount, bringing the total down to $16.96 or so
2) Share the linode with someone else, bringing the total per person down to $8.48
You can even split things up further. Generally it's not recommended to do virtualization on top of virtualization, but it is possible to use OpenVZ on top of Xen. Another simpler approach (that requires you to trust your colleague with root access) is to just set up two chroot jails on the linode, one for each of you. Anybody who has root access inside a chroot jail will have root access outside of it, but you can at least get two different environments that let each of you do your own thing, potentially even with different IP addresses (although getting a second IP from Linode might be tricky).