I'd use the first solution, but use TPIC6C595 instead. Much cheaper. You'll need diodes, though, they're not built in. But diodes are cheap.
Who cares about the wasted current? It's a little pulse once in a great while.
You can save on wasted current a bit by using a 10V rail and dropping 5V in a 180 ohm resistor. That way the current is the same (27.8 mA) and the power wasted is only 138 mW in one resistor, 556 mW in the other. If you use that trick exactly, if for example the relay needs at least 4.5V to switch and you use a 5V rail, you'll need to use 18 ohm resistors, not 50, and the low side will draw 277 mA and burn 1.4 W. The exact "sweet spot" (not necessarily 10V) will depend on the relay's requirements, of course.
Edited to correct derpy math.