Are there strategies or techniques to create HA environment when IP failover isn't available? I'm reading a guide at Linode's library which describes exactly what I want to do, but I'm not sure my current VPS host supports IP failover.
IP failover using hearbeat/pacemaker requires the ability to move an IP address between nodes. If your VPS provider locks you into a single IP address, then that isn't the route you want to take. You'll need something where the IP address is stable.
Depending on what you're doing, something like haproxy may fill your needs. You place a server running a very simple service in front of a pair of server (or more), and clients talk to the haproxy server. Should a failover be needed, the haproxy server flips its back end communication to the still-working server. It does introduce a single point of failure, but it's a fairly simple service which may very well be more stable than the application you're hoping to make highly available.
HAProxy is just one of several ways of doing this, but it is a software-only load-balancer which is much more compatible than a hardware load-balalncer like an F5 device.
You could use Round-robin DNS.
The solutions that would be viable really depend on what the application is though.