Here is a short manual how to create a correctly aligned partition with parted (thanks to aadamowski):
(WARNING: the instructions below will likely destroy any data that's
on the given drive, only do this with drives you're intending to
erase):

# parted /dev/YOUR_DEVICE_NAME

(parted) mklabel gpt
# Here ^ I've chosen the GPT partition table format, but others may be
OK too - untested by me.

(parted) unit s
# Here ^ we're choosing sectors as units of measurement

(parted) mkpart primary ext2 40 -1
# Here ^ we're creating a partition that starts at sector 40, which is
divisible by 8.
# You can also try 48, 56, 64 and others - these should offer the same
high performance,
# but some space will go to waste - it's only some tiny kilobytes, though.

# Parted will likely complain about the end location of the ending sector:
Warning: You requested a partition from 40s to 2930277167s.
The closest location we can manage is 40s to 2930277134s.
Is this still acceptable to you?
Yes/No?
# Of course, we answer Yes.

(parted) quit

# After that, create a filesystem as usual, e.g:
# mkfs.ext4 -T largefile4 /dev/YOUR_DEVICE_NAME

This should get the optimum performance from your 4 kB physical sector
drives even when they report 512 B sectors only to the OS.
 
 
If you prefer to use fdisk follow these steps (they come from ted):
 
 fdisk -H 224 -S 56 /dev/sdb
 running fdisk with these parameters ensures that every partition you create is aligned to 4KiB boundries.