Segue abaixo um exemplo de configuração para PPPoE, que já testei com ASDL da Telefonica (Speedy).
NÃO SEI SE O VELOX USA PPPoE ou PPPoA. Se for PPPoA a configuração deve mudar um pouco...
access-list 1 permit 192.168.1.0 0.0.0.255
interface Dialer0
exit
default interface Dialer0
interface Dialer0
ip mtu 1452
no shutdown
ip address negotiated
ip nat outside
dialer pool 1
dialer-group 1
encapsulation ppp
dialer idle-timeout 120
dialer fast-idle 20
ppp authentication pap callin
ppp pap sent-username username@proverdor.com.br password 0 12345
exit
interface FastEthernet0/1
description $ETH-WAN$
no shutdown
pppoe-client dial-pool-number 1
pppoe enable
exit
ip nat inside source list 1 interface Dialer0 overload
ip route 0.0.0.0 0.0.0.0 Dialer0 1
dialer-list 1 protocol ip permit
! IP address / user account command
interface FastEthernet0/0
ip address 192.168.1.0 255.255.255.0
ip tcp adjust-mss 1412
ip nat inside
exit